Find the Lexicographically Smallest List

You are given a list of n integers. It is known that these integers originally formed a list from which a left rotation and a right rotation were applied, and then the results were shuffled. Your task is to recover the lexicographically smallest list L that could have produced the given array. In other words, simply sort the list in non-decreasing order.

The solution can be formally expressed as follows:

Let \(A = [a_1, a_2, \dots, a_n]\) be the input array. Find \(L = [l_1, l_2, \dots, l_n]\) such that \(L\) is the sorted order of \(A\), i.e., \[ l_1 \le l_2 \le \dots \le l_n \]

The final output should be printed as the sorted list with each integer separated by a single space.

inputFormat

The first line of the input contains a single integer n representing the number of elements in the list. The second line contains n space-separated integers.

outputFormat

Output the lexicographically smallest list (i.e., the sorted list) in a single line with each integer separated by a space.

8
2 1 6 4 5 3 7 8

1 2 3 4 5 6 7 8