Count every distinct array value and report values in the order in which they first appear.

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 1000\)

Output

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

Example

Input

1
16

Output

16 1