An airfield's runway edge-light controller reports n lamp brightness readings, given in the order the lamps currently sit along the runway centerline. The controller's auto-leveling firmware silently dims or brightens any interior lamp whose brightness exactly equals the average of its two immediate neighbors, treating it as a redundant gradient point — and every time that happens it corrupts the maintenance log. Ground crew always avoids this by physically re-seating the lamps according to one fixed rule: sort all n readings into non-decreasing order, then split that sorted list into a low group holding the first ceil(n/2) values (kept in that sorted order) and a high group holding the remaining values (also kept in that sorted order); finally interleave them back into a single row by placing the low group's values, in order, at positions 0, 2, 4, ... and the high group's values, in order, at positions 1, 3, 5, .... Apply this rule to the given readings and report the resulting row.

Input format

• Line 1: a single integer n — the number of lamps.
• Line 2: n space-separated integers, the current brightness readings, left to right.

Output format

Print the n brightness readings in the new row order produced by the rule above, space-separated on one line.

Constraints

• 1 <= n <= 100000
• 0 <= brightness <= 100000

5
9 1 4 7 3

1 7 3 9 4

4
2 2 2 2

2 2 2 2