Zigzag Sequence Rearrangement

Given an integer array of size \(n\), rearrange its elements to form a zigzag sequence. In a zigzag sequence, the numbers are arranged by alternately selecting the smallest and the largest elements from the sorted order of the array. More formally, if the sorted array is \(a_1, a_2, \ldots, a_n\), then the desired output is \(a_1, a_n, a_2, a_{n-1}, \ldots\). Print the sequence as a space-separated list.

inputFormat

The input is given via standard input (stdin). The first line contains an integer \(n\) (\(1 \le n \le 10^5\)) representing the number of elements in the array. The second line contains \(n\) space-separated integers.

outputFormat

Output the zigzag rearranged sequence as a single line of space-separated integers to standard output (stdout).

7
4 3 7 8 6 2 1

1 8 2 7 3 6 4