Count every distinct array value.

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 distinct value x in increasing order, print x - f, where f is its frequency.

Example

Input

5
3 1 3 2 5

Output

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