Maximize Minimum Difference

Given an array of unique integers, rearrange the elements such that the minimum difference between any two consecutive elements is maximized. In other words, you are to maximize \(\min_{1 \leq i < n} |a_i - a_{i+1}|\). A common approach is to first sort the array and then construct a new sequence by alternately picking the smallest and largest remaining elements.

For example, given the array [1, 5, 10, 15], one valid rearrangement is [1, 15, 5, 10].

inputFormat

The first line contains an integer \(n\) (\(n \geq 2\)) denoting the number of elements. The second line contains \(n\) space-separated unique integers.

outputFormat

Output the rearranged array as a sequence of space-separated integers (in one line).

4
1 5 10 15

1 15 5 10