Rearrange Array into Wave Form

Given an array of integers, transform the array into a wave form such that every second element (i.e. at every odd index) is greater than its adjacent neighbors. In other words, for an array (a_0, a_1, \ldots, a_{n-1}), for every odd index (i) (with (1 \le i \le n-2)), the condition (a_i > a_{i-1}) and (a_i > a_{i+1}) must hold.

For example, if the input array is [1, 2, 3, 4, 5, 6], one valid rearrangement is [1, 3, 2, 5, 4, 6].

The constraints allow the array to be large and the element values to be high, so efficient sorting and swapping methods should be used.

inputFormat

The input is given in two lines. The first line contains a single integer (n) which represents the number of elements in the array. The second line contains (n) space-separated integers representing the elements of the array.

outputFormat

Output the rearranged array in a single line. The elements should be printed in order separated by a single space.## sample

6
5 6 1 3 8 2

1 3 2 6 5 8