Zigzag Sequence

You are given an array of integers. Your task is to rearrange the array into a zigzag sequence such that the resulting sequence satisfies the pattern:

\( a_0 < a_1 > a_2 < a_3 > \dots \)

In other words, for every even index \(i\) (0-indexed), the element \(a_i\) should be less than the following element (if it exists), and for every odd index, \(a_i\) should be greater than the following element (if it exists).

Example: For the array [4, 3, 7, 8, 6, 2, 1], the zigzag sequence is [3, 7, 4, 8, 2, 6, 1].

inputFormat

The input is given via standard input (stdin). The first line contains an integer (n), representing the number of elements in the array. The second line contains (n) space-separated integers denoting the elements of the array.

outputFormat

Output the rearranged zigzag sequence as a list of space-separated integers to standard output (stdout).## sample

7
4 3 7 8 6 2 1

3 7 4 8 2 6 1