Rearrange Array to Form Wave Pattern

You are given an array of integers. Your task is to rearrange the elements of the array so that every odd-indexed element (i.e. the element at position 1, 3, 5, … in 0-indexing) is greater than its adjacent elements. Formally, for each odd index \(i\) (where \(0 \leq i < n\)), if \(i-1\) and \(i+1\) exist, the condition

[ arr[i] > arr[i-1] \quad \text{and} \quad arr[i] > arr[i+1] ]

must hold. It is guaranteed that by a valid rearrangement, a solution always exists. Print the final rearranged array. Note that if there are multiple possible answers, you may output any one of them.

Example:

Input:
7
4 3 7 8 6 2 1
Output:
3 7 4 8 2 6 1

</p>

inputFormat

The first line contains a single integer \(n\), the number of elements in the array. The second line contains \(n\) space-separated integers representing the elements of the array.

outputFormat

Output the rearranged array in a single line with each element separated by a space. The array should satisfy that every odd-indexed element (1-indexed: 2nd, 4th, etc. in natural order) is greater than its left and right neighbors.

## sample

5
1 2 3 4 5

1 3 2 5 4