Rearrange Array: Largest and Smallest Alternation

Given an array of integers, rearrange it in such a way that the largest number is followed by the smallest number, the second largest is followed by the second smallest, and so on. More formally, let \(A\) be the input array and let \(A^*\) be the sorted array in increasing order. Your task is to construct a new array \(B\) such that:

[ B = [A^[n], A^[1], A^[n-1], A^[2], \ldots]]

If the number of elements is odd, the middle element will appear at the end of \(B\). This problem must be solved using standard input and output.

inputFormat

The first line of input contains an integer \(n\) (\(0 \le n \le 10^5\)) representing the number of elements in the array. The second line contains \(n\) space-separated integers. If \(n = 0\), the second line will be empty.

outputFormat

Output a single line of \(n\) space-separated integers representing the rearranged array according to the described pattern.

5
1 2 3 4 5

5 1 4 2 3