Develop the Quick Sort algorithm on an integer list ~A~.

Input

• The first line is an integer ~N~ (~1~ ≤ ~N~ ≤ ~10^{5}~), the number of integers.

• The ith line of the next ~N~ lines contains the integer (~0~ ≤ ~A_{i}~ ≤ ~10^{9}~).

Output

• Output ~N~ rows, each row contains the integer in an ascending order.

Sample Input

5

5 4 1 0 3

Sample Output

0 1 3 4 5