01204212/like

This is part of 01204212

You want to keep track of the number of "likes" each status has. In the beginning, every status has 0 likes. You are given a sequence of like clicks (as a sequence of status IDs).

Input

• First line: an integer N (1<=N<=100,000)
• The next N lines: each line contains an integer x, the ID of the post clicked.

Output

There are N lines of output, each contains the current number of likes the post ID x has so far (including this one).

Example

Input

10
4
2
4
10
100
30
10
35
4
200

Output

1
1
2
1
1
1
2
1
3
1

Test data

Use the test data for ID requests

Download at: here

Solution to n10.in

1
1
1
1
1
1
1
2
1
2

Solution to n1000.in (first 20 lines)

1
1
1
1
1
2
1
1
1
1
1
2
3
1
2
1
4
2
1
1

Code

Collections: you will have to use the Map interface. These are implementations:

• TreeMap
• HashMap