Đếm tần suất

Cho dãy gồm \(n\) số nguyên \(a_1, a_2, \ldots, a_n\). Với mỗi giá trị xuất hiện trong dãy, hãy cho biết nó xuất hiện bao nhiêu lần.

Lưu ý: các giá trị có thể âm và rất lớn, nên không dùng được mảng đếm thông thường.

Input

• Dòng đầu chứa số nguyên \(n\) (\(1 \le n \le 2 \cdot 10^5\)).
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \ldots, a_n\) (\(|a_i| \le 10^9\)).

Output

• In mỗi giá trị khác nhau trên một dòng, theo thứ tự giá trị tăng dần. Mỗi dòng gồm giá trị và số lần xuất hiện, cách nhau một dấu cách.

Scoring

• Có \(40\%\) số test với \(0 \le a_i \le 10^6\).

Sample Input 1

8
1000000000 -5 7 7 -5 7 0 1000000000

Sample Output 1

-5 2
0 1
7 3
1000000000 2