Count each distinct value in an array.

Input

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

The input satisfies:

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

Output

For each distinct value \(x\) in increasing order, print x - frequency on its own line.

Example

Input

5
3 1 3 2 5

Output

1 - 1
2 - 1
3 - 2
5 - 1