Reorder Array: Maximizing Even-Indexed Elements

You are given an array of n integers. Your task is to reorder the array so that for every even index i (0-indexed), the element at that index is greater than its adjacent elements. Formally, for every even i:

• If i > 0, then \(a_i > a_{i-1}\).
• If i+1 < n, then \(a_i > a_{i+1}\).

It is guaranteed that there is at least one valid reordering. If there exist multiple valid answers, any of them will be accepted.

inputFormat

The first line contains a single integer n \((1 \leq n \leq 10^5)\), 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 reordered array with n space-separated integers. The output must satisfy that for every even index i, if i > 0 then \(a_i > a_{i-1}\) and if i+1 < n then \(a_i > a_{i+1}\).

1
1

1