Cho một dãy gồm ~n~ số nguyên dương ~A_1, A_2, ..., A_n~.

Yêu cầu: Hãy in ra tất cả các số trong mảng A cùng với số lần xuất hiện của chúng.

Input

• Dòng đầu gồm số nguyên dương ~n~ (~n \leq 10^5~).
• Dòng tiếp theo chứa ~n~ số nguyên ~A_1, A_2, ... A_n~ (~A_i \leq 10^7~).

Output

• Gồm ~n~ dòng, mỗi dòng ghi số hạng thứ ~A_i~ và số lần xuất hiện của chúng.

Sample Input

9
2 3 1 2 3 4 5 4 3

Sample Output

2 2
3 3
1 1
2 2
3 3
4 2
5 1
4 2
3 3