Wiggle Sort

Given an array of integers, rearrange the array so that it becomes wiggle sorted. An array is said to be wiggle sorted if it satisfies:

\(a_0 \le a_1 \ge a_2 \le a_3 \ge a_4 \ldots\)

You are required to modify the array in-place using the following strategy: for every index i from 0 to \(n-2\), if \(i\) is even and \(a_i > a_{i+1}\), or if \(i\) is odd and \(a_i < a_{i+1}\), swap \(a_i\) and \(a_{i+1}\). This ensures that the required wiggle sort condition holds.

The input is read from standard input and the output should be printed to standard output.

inputFormat

The first line contains a single integer \(n\) (\(1 \le n \le 10^5\)), the number of elements in the array.

The second line contains \(n\) integers separated by spaces, representing the elements of the array. The elements can range from \(-10^9\) to \(10^9\).

outputFormat

Output the wiggle sorted array. The numbers should be printed in a single line separated by a space. It is guaranteed that a valid answer exists.

6
3 5 2 1 6 4

3 5 1 6 2 4