Minimize Sum of Absolute Differences

Given a list of distinct integers, rearrange the array such that the sum of absolute differences between consecutive elements is minimized. Mathematically, if the rearranged array is (b_1, b_2, \ldots, b_n), then the objective is to minimize (\sum_{i=1}^{n-1} |b_{i+1} - b_i|). It can be proven that arranging the numbers in non-decreasing order achieves this minimum.

For example, if the input array is [3, 1, 4, 9, 2], the optimal rearrangement is [1, 2, 3, 4, 9].

inputFormat

The input consists of two lines. 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 distinct integers.

outputFormat

Output the rearranged array in non-decreasing order. The elements should be printed on a single line separated by spaces.## sample

5
3 1 4 9 2

1 2 3 4 9