Peak Array Rearrangement

Given an array of integers, rearrange its elements to form a peak array. A peak array satisfies the following condition: for every odd index \(i\) (0-indexed), the element at that position is strictly less than its left neighbor and, if it exists, its right neighbor. In other words, for every odd \(i\) (i.e. \(i = 1, 3, 5, \dots\)), the following must hold:

[ a[i] < a[i-1] \quad \text{and} \quad \text{if } i+1 < n,\ a[i] < a[i+1] ]

If it is impossible to rearrange the given array into a valid peak array, output an empty array: [].

inputFormat

The input is given in two lines. The first line contains an integer \(n\), the number of elements in the array. The second line contains \(n\) space-separated integers.

outputFormat

If a valid peak array rearrangement exists, print the rearranged array as a sequence of space-separated integers in one line. If no valid rearrangement exists, print [].

6
3 1 2 7 4 6

7 1 6 2 4 3