Rearrange Array

Given an array of n integers, rearrange the array so that the difference between any two consecutive elements is minimized. If there are multiple valid rearrangements, return the lexicographically smallest one. In this problem, the lexicographically smallest arrangement is achieved by simply sorting the array in non-decreasing order.

Note: The solution must read the input from stdin and output the result to stdout.

The mathematical objective can be formally stated as follows:

Find a permutation \(p\) of the array \(a\) such that \( \sum_{i=1}^{n-1} |p_i - p_{i+1}| \) is minimized. In the event of ties, choose the permutation \(p\) that is lexicographically smallest. It can be shown that sorting the array yields this optimal permutation.

inputFormat

The first line contains an integer n denoting 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 of space-separated integers.

5
3 1 4 1 5

1 1 3 4 5