Rearrange List by Index Sorting

Given a list of n integers, rearrange the list so that the elements at even indices (0-based) are sorted in ascending order, while the elements at odd indices are sorted in descending order.

The input consists of an integer n, followed by a line containing n space-separated integers. The output should be the rearranged list, printed on a single line with each number separated by a space.

More formally, let the original list be \(a_0, a_1, \dots, a_{n-1}\). Let \(E\) be the sorted list (in increasing order) of elements at even indices, and \(O\) be the sorted list (in decreasing order) of elements at odd indices. Then the output list \(b\) is defined as:

\(b_i = \begin{cases} E_{i/2} & \text{if } i \text{ is even}\\ O_{(i-1)/2} & \text{if } i \text{ is odd} \end{cases}\)

inputFormat

The first line contains an integer (n) ((1 \leq n \leq 10^5)), representing the number of integers. The second line contains (n) space-separated integers.

outputFormat

Print the rearranged list on a single line with elements separated by a single space.## sample

8
9 4 6 7 3 8 5 10

3 10 5 8 6 7 9 4