Zigzag Array Rearrangement

Given an array of n integers, your task is to rearrange the array into a zigzag pattern. In particular, for every even index i (0-based indexing), the element at that index should be less than or equal to the element at index i+1 (if it exists), i.e., \(A[i] \le A[i+1]\). Similarly, for every odd index i, the element should be greater than or equal to the element at index i+1 (if it exists), i.e., \(A[i] \ge A[i+1]\).

You are required to achieve the rearrangement in a single traversal of the array. The final array should satisfy the zigzag condition:

• If i is even: \(A[i] \le A[i+1]\)
• If i is odd: \(A[i] \ge A[i+1]\)

It is guaranteed that there exists at least one valid rearrangement. In case of multiple valid outcomes, your program only needs to output one of them.

inputFormat

The input is given via standard input (stdin) and consists of two lines:

1. The first line contains an integer n representing the number of elements in the array.
2. The second line contains n space-separated integers, representing the elements of the array.

outputFormat

Output the rearranged array as a single line of space-separated integers via standard output (stdout).

## sample

6
4 3 7 8 6 2

3 7 4 8 2 6

</p>