Cho mảng A gồm N phần tử. Hãy đếm tần số xuất hiện của mỗi giá trị trong mảng và in ra theo thứ tự tăng dần của giá trị.

Sử dụng kỹ thuật rời rạc hoá (hoặc hash map) để xử lý các giá trị lớn.

Đầu vào

• Dòng đầu tiên chứa số nguyên N (1 ≤ N ≤ 10^5).
• Dòng thứ hai chứa N số nguyên A_i (-10^9 ≤ A_i ≤ 10^9).

Đầu ra

In ra nhiều dòng, mỗi dòng gồm giá trị và tần số tương ứng, cách nhau bởi dấu cách. Các giá trị được in theo thứ tự tăng dần.

Ví dụ

Input:
8
3 1 4 1 5 9 2 6

Output:
1 2
2 1
3 1
4 1
5 1
6 1
9 1