Count every distinct integer and report frequencies in the order the values first appear.

Input

The first line contains n (1 ≤ n ≤ 1000000). The second line contains n integers |aᵢ| ≤ 10^9.

Output

First print the number of distinct values. Then print value and frequency pairs in first-appearance order.

Examples

Input #1

6
5 3 2 3 2 2

Output #1

3
5 1
3 2
2 3

Input #2

1
9

Output #2

1
9 1