Count every distinct array value while preserving first-appearance order.

Input

The first line contains n. The second line contains n integers.

Array and query counts are between $1$ and $10^5$. Integer values are between $-10^9$ and $10^9$. Deleting a missing multiset value has no effect.

Output

For each value x, the first time it occurs in the array, print x f, where f is its total frequency.

Example

Input

7
4 2 6 3 0 7 7

Output

4 1
2 1
6 1
3 1
0 1
7 2