Rearrange Array to Minimize Maximum Adjacent Difference

You are given an array of n integers. Your task is to rearrange the elements of the array so that the maximum absolute difference between any two adjacent elements is minimized. In other words, you need to find an arrangement of the array such that if the rearranged array is a₁, a₂, \(\ldots\), a_n, then the value

[ \max_{1 \le i < n} \left|a_{i+1} - a_i\right| ]

is as small as possible.

Hint: For many cases, simply sorting the array in non-decreasing order will yield the desired arrangement.

inputFormat

The input is given via stdin and consists of two lines:

• The first line contains an integer n (1 ≤ n ≤ 10⁵), representing the number of elements in the array.
• The second line contains n space-separated integers, each representing an element of the array. The absolute values of the elements do not exceed 10⁹.

outputFormat

Output the rearranged array as a single line to stdout. The elements should be separated by a single space. It is guaranteed that the arrangement which minimizes the maximum adjacent difference is unique (for example, by simply sorting the array in non-decreasing order).

5
3 8 1 6 7

1 3 6 7 8