Count each distinct value and preserve the order in which values first appear.

Input

The first line contains \(n\). The second line contains \(n\) integers.

The input satisfies:

• \(1 <= n <= 1000\)

Output

For each distinct value, print the value and frequency separated by one space, in first-appearance order.

Example

Input

7
7 3 7 0 1 3 7

Output

7 3
3 2
0 1
1 1