Cho một dãy gồm \(n\) số nguyên dương \(A_1,A_2,\ldots,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 chứa số \(n\) (\(n\leq 10^5\)).
• Dòng thứ hai chứa \(n\) số nguyên dương \(A_1,A_2,\ldots,A_n\) (\(A_i\leq 10^6\)).

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.

Example

9
2 3 1 2 3 4 5 4 3

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