Minimize Absolute Differences

Given a sequence of n unique integers, rearrange the sequence so that the sum of the absolute differences between every two consecutive elements is minimized. Mathematically, if the rearranged sequence is \(a_1, a_2, \dots, a_n\), you need to minimize \(\sum_{i=1}^{n-1} |a_{i+1}-a_i|\). It can be shown that the optimal solution is to output the numbers in sorted order.

Example: For the input sequence [4, 2, 1, 3, 5], the minimal arrangement is [1, 2, 3, 4, 5].

inputFormat

The first line contains an integer (n) representing the number of integers. The second line contains (n) space-separated integers representing the sequence.

outputFormat

Output the rearranged sequence as (n) space-separated integers in a single line.## sample

5
4 2 1 3 5

1 2 3 4 5