Description

In a research survey, $n$ natural numbers were collected, each not exceeding $1.5 \times 10^9$. It is known that the number of distinct values does not exceed $10^4$. Now you need to count how many times each natural number appears and output the results in ascending order of the numbers.

Input Format

There are $n+1$ lines in total.

• The first line contains an integer $n$, the number of natural numbers.
• Lines $2$ to $n+1$ each contain one natural number.

Output Format

Output $m$ lines in total (where $m$ is the number of distinct numbers among the $n$ natural numbers), in ascending order of the numbers.

Each line outputs $2$ integers: the natural number and the number of times it appears, separated by a single space.

8
2
4
2
4
5
100
2
100

2 3
4 2
5 1
100 2

Hint

• 30% of the testdata satisfy: $1 \le n \le 1000$.
• 60% of the testdata satisfy: $1 \le n \le 50000$.
• 100% of the testdata satisfy: $1 \le n \le 200000$, and each number does not exceed $1.5 \times 10^9$.

NOIP 2007 Senior, Problem 1.

Translated by ChatGPT 5