Frequency Count of Natural Numbers

Given a sequence of n natural numbers, each not exceeding \(1.5 \times 10^9\), and knowing that there are at most \(10^4\) distinct numbers, you are required to count the frequency of each number. Output the results in ascending order of the natural numbers.

inputFormat

The first line contains a single integer n indicating the number of natural numbers. The second line contains n natural numbers separated by spaces.

outputFormat

For each distinct natural number, output a line with the number and its frequency separated by a space. The output should be sorted in ascending order of the numbers.

sample

5
1 2 2 1 3

1 2
2 2
3 1