Arrange Array to Minimize Adjacent Differences

You are given an array of n integers. Your task is to rearrange the array elements so that the difference between any two consecutive elements is minimized. In other words, by placing the numbers in the optimal order, the adjacent differences are as small as possible.

If there are multiple valid arrangements that achieve the minimum adjacent differences, you should output the lexicographically smallest arrangement. It can be shown that simply sorting the array in non-decreasing order will satisfy these conditions.

Input/Output: The solution must read the input from standard input (stdin) and write the output to standard output (stdout).

Mathematical Explanation:
After sorting the array, let the sorted array be \(a_1, a_2, \ldots, a_n\). The sum of adjacent differences is \(\sum_{i=1}^{n-1} (a_{i+1} - a_i)\). This sum is minimized when the array is in sorted order. Moreover, if multiple arrangements exist, the sorted order is lexicographically smallest.

inputFormat

The first line of input contains a single integer \(n\) representing the number of elements in the array.

The second line contains \(n\) space-separated integers representing the elements of the array.

outputFormat

Output the rearranged array as a single line with \(n\) space-separated integers, which is the lexicographically smallest arrangement that minimizes the difference between any two adjacent numbers.

4
4 2 1 3

1 2 3 4