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