Rearrange Array

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

In other words, if the rearranged array is \(A\) with indices \(0, 1, 2, \dots\), then the subsequence \(A[0], A[2], A[4], \dots\) must satisfy \(A[0] \le A[2] \le A[4] \le \cdots\), and the subsequence \(A[1], A[3], A[5], \dots\) must satisfy \(A[1] \ge A[3] \ge A[5] \ge \cdots\).

For example, if the input array is [1, 3, 2, 8, 5, 7], then the rearranged array should be [1, 8, 2, 7, 5, 3].

inputFormat

The first line contains an integer \(n\) representing 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 containing the rearranged array with its elements separated by a space.

6
1 3 2 8 5 7

1 8 2 7 5 3