Rearrange Sequence Alternating Extremes

You are given a sequence of n integers. Rearrange the sequence so that the elements are ordered in an alternating pattern of the maximum and minimum remaining elements. More formally, if the sorted sequence is \(a_1 \leq a_2 \leq \ldots \leq a_n\), then the required rearrangement is \(a_n, a_1, a_{n-1}, a_2, \ldots\).

If \(n = 0\), the output should be empty. Otherwise, if there is a single middle element, it should be output last.

Example:

Input: 6
       1 3 5 6 9 8
Output: 9 1 8 3 6 5

inputFormat

The first line of input contains an integer \(n\) which represents the number of elements in the sequence. The second line contains \(n\) space-separated integers.

outputFormat

Output a single line with the rearranged sequence. The elements should be separated by a single space. If \(n = 0\), output nothing.

6
1 3 5 6 9 8

9 1 8 3 6 5