Wave Array Sorting

You are given an array of n integers. Your task is to rearrange the array into a wave-like form. A wave array is defined as an array where the elements at even indices are greater than or equal to their adjacent odd-indexed elements. In other words, the rearranged array b must satisfy:

\(b_1 \ge b_2 \le b_3 \ge b_4 \le \dots\)

You must form the wave by first sorting the array in non-decreasing order, and then swapping every pair of adjacent elements (i.e. swap a[0] with a[1], a[2] with a[3], and so on). This guarantees that the wave condition holds for the entire array.

The input will be read from standard input and the resulting wave sorted array should be printed to standard output, with elements separated by a space.

inputFormat

The first line of input contains a single integer n representing the number of elements in the array. The second line contains n space-separated integers representing the elements of the array.

outputFormat

Print the elements of the wave sorted array in one line separated by a space.

6
3 6 5 10 7 20

5 3 7 6 20 10