Rearrange Array for Maximum Absolute Difference

You are given an array of integers. Your task is to rearrange the array such that the sum of the absolute differences between consecutive elements is maximized.

The objective is to maximize the value:

One simple strategy to achieve a near-optimal solution is to first sort the array. Then, select elements alternately from the beginning and the end of the sorted array. For example, given the input array [1, 2, 4], one possible rearrangement is [1, 4, 2].

If there are duplicate values or only one element exists, the rearranged array remains the same as the input.

inputFormat

The input is given via standard input (stdin). The first line contains a single integer n (1 ≤ n ≤ 10⁵), which is the number of elements in the array. The second line contains n space-separated integers, each representing an element of the array.

outputFormat

Output the rearranged array as a single line of space-separated integers to standard output (stdout).

3
1 2 4

1 4 2