Rearrange Sequence to Minimize Absolute Difference

You are given a sequence of n integers. Your task is to rearrange this sequence so that the sum of absolute differences between consecutive elements is minimized. In other words, you must minimize the value:

$$S = \sum_{i=1}^{n-1} \left|a_{i+1} - a_{i}\right|$$

It can be proven that the optimal solution is to sort the sequence in non-decreasing order.

inputFormat

The input is read from stdin and has the following format:

• The first line contains a single integer n which represents the number of elements in the sequence.
• The second line contains n space-separated integers representing the elements of the sequence.

outputFormat

Output the rearranged sequence in one line to stdout, where the numbers are separated by a single space. This arrangement minimizes the sum:

$$S = \sum_{i=1}^{n-1} \left|a_{i+1} - a_{i}\right|$$

4
4 2 1 3

1 2 3 4