Given a list of integers, output the list in ascending order of distinct values and the corresponding number of occurrences of the value.

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

• Each line contains a value and the number of occurrences of the value.

Sample Input

8

0 4 3 1 5 6 1 3

Sample Output

0 1

1 2

3 2

4 1

5 1

6 1