C. New Sorting Algorithm
time limit per test
15 seconds
memory limit per test
8 megabytes
input
standard input
output
standard output

Michael is on a crunch so he gives you a permutation of $$$n$$$ numbers to sort.

He wants you to sort it quickly and efficiently, but it seems like none of the current sorting algorithms are working for him. As the master of computational science and analysis, he has enlisted your help.

Help him do this!

Input

The first line contains $$$n$$$ the number of numbers Michael wants you to sort. $$$1 \leq n \leq 5\cdot 10^6$$$.

The second line contains the numbers $$$a_1, a_2, ..., a_n$$$, $$$1 \leq a_i \leq n$$$.

Output

Output $$$n$$$ integers, the numbers sorted.

Note

Credit: DanielQiu