Rearrange Array to Minimize Adjacent Difference

You are given an array of n integers. The task is to rearrange the elements such that the absolute difference between any two consecutive elements is minimized. In other words, if the rearranged array is \(A = [a_1, a_2, \dots, a_n]\), then the objective is to minimize \(|a_2-a_1|, |a_3-a_2|, \dots, |a_n-a_{n-1}|\). It turns out that sorting the array in non-decreasing order achieves this.

Your program should read the input from stdin and output the rearranged array to stdout. The first line of input contains a single integer n, indicating the number of elements. The second line contains n space-separated integers. The output should be a single line containing the sorted array with each element separated by a space.

inputFormat

The input is read from stdin and consists of two lines:

1. The first line contains an integer n (\(1 \leq n \leq 10^5\)), the number of elements in the array.
2. The second line contains n space-separated integers, each of which can be negative or positive.

outputFormat

Output the rearranged array to stdout in one line. The array should be sorted in non-decreasing order and each number should be separated by a single space.

4
4 2 1 3

1 2 3 4