Given a sequence of ~n~ positive integers ~A_1, A_2,..., A_n~ , you are required to print each unique element of the array along with its frequency in increasing order. Each unique number should only appear once in the output.

Input:

• The first line contains an integer ~n~ ~(n≤10^5)~, the number of integers in the sequence.
• The second line contains n positive integers ~A_1, A_2,..., A_n~ ~(A_i≤10^6)~.

Output:

• Print many lines. Each line should contain a unique element followed by its frequency of occurrence in the input sequence.

Sample Input

8
9 7 2004 97 7 9 200 4

Sample Output

4 1
7 2
9 2
97 1
200 1
2004 1