Rearrange Array to Minimize Absolute Differences

Given an array of n integers, rearrange the elements so that the sum of the absolute differences between adjacent elements is minimized. The optimal solution is to sort the array in non-decreasing order.

In mathematical terms, if the rearranged array is \(a_1, a_2, ..., a_n\), the cost is \(\sum_{i=1}^{n-1} |a_{i+1} - a_i|\). Sorting the array minimizes this cost.

inputFormat

The first line contains an integer n ( \(0 \le n \le 10^5\)), the number of elements in the array.

The second line contains n integers separated by spaces, representing the elements of the array.

outputFormat

Output the rearranged array in non-decreasing order. The numbers should be separated by a single space.

5
3 1 4 1 5

1 1 3 4 5