Count the frequency of every distinct value in an integer array.

Input

The first line contains \(N\). The second line contains \(N\) integers \(A_i\).

The input satisfies:

• \(1 \le N \le 1000\)
• \(0 \le A_i \le 10^7\)

Output

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

Example

Input

1
2

Output

2 - 1