Given a list of integers, output the list in ascending order. If two numbers are equals, keep the order of them in the input.

Input

• The first line contains one integer ~N~ - the number of integers (~1~ ≤ ~N~ ≤ ~10^{5}~).

• The next line contains ~N~ integers which do not exceed ~10^{9}~.

Output

• Include ~N~ lines, each line is an integer and the its index in the input.

Sample Input

5

4 1 0 2 1

Sample Output

0 2

1 1

1 4

2 3

4 0