Rearranged Array

You are given an array of n integers. Your task is to rearrange the array such that the elements at even indices (0-indexed) are in non-decreasing order and the elements at odd indices are in non-increasing order.

In other words, if the original array is \(A = [a_0, a_1, a_2, \dots, a_{n-1}]\), then after rearrangement, the subsequence \(E = [a_0, a_2, a_4, \dots]\) must be sorted in non-decreasing order and the subsequence \(O = [a_1, a_3, a_5, \dots]\) must be sorted in non-increasing order. The final array is then formed by interweaving the two subsequences.

For example, if you are given the array [3, 5, 2, 1, 6, 4], the correct rearranged array is [2, 5, 3, 4, 6, 1].

inputFormat

The first line contains an 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 a single line with the rearranged array, where the integers are space-separated.

6
3 5 2 1 6 4

2 5 3 4 6 1