Rearrange Array by Alternating Maximum and Minimum Elements

You are given an array of n integers. Your task is to rearrange the array so that every maximum element (from the remaining elements) is immediately followed by the minimum element (from the remaining elements). Formally, let \(a_1, a_2, \dots, a_n\) be the sorted order of the given array. Then, the rearranged order should be:

a_n, a_1, a_{n-1}, a_2, \ldots

If there is an odd number of elements, the middle element remains at the end. Print the rearranged array as space-separated integers.

inputFormat

The first line contains an integer \(n\) (1 \(\leq n \leq 10^5\)) denoting the number of elements in the array.

The second line contains \(n\) space-separated integers \(a_1, a_2, \dots, a_n\) where each \(a_i\) satisfies \(|a_i| \leq 10^9\).

outputFormat

Output a single line containing the rearranged array. The numbers should be separated by a single space.

6
1 2 3 4 5 6

6 1 5 2 4 3