Cho dãy ~A~ gồm ~N~ số nguyên ~A_1, A_2, …, A_N~. Tần số của một số là số lần xuất hiện của số đó trong dãy ~A~. Ví dụ: dãy số 1 1 2 2 2 1 3 7, thì số 1 có tần số bằng 3, số 2 có tần số bằng 3, số 3 và 7 có tần số bằng 1. Nhiệm vụ của bạn là viết chương trình với dãy ~A_1, A_2, …, A_N~, hãy đưa ra tần số xuất hiện của mỗi phần tử

INPUT:

• Dòng 1 chứa số nguyên dương ~N~ (~1 ≤ N ≤ 10^5~)
• Dòng 2 chứa ~N~ số nguyên ~A_1, A_2, …, A_N~ (với ~|Ai| ≤ 10^9~)

OUPUT:

Đưa ra tần số xuât hiện của mỗi số trong dãy theo thứ tự tăng dần

Ví dụ:

Input

10
1 -1 2 7 2 2 -1 3 7 7

Output

-1 2

1 1

2 3

3 1

7 3