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

You can use the same Main class from task ID request

Code for your own implementation of binary search trees

TreeNode

public class TreeNode {
    public int key;
    public int val;
    public TreeNode leftChild;
    public TreeNode rightChild;
	
    public TreeNode(int k, int v) {
        key = k;
        val = v;
        leftChild = rightChild = null;
    }
}

An example of find

    private TreeNode find(TreeNode node, int key) {
        if(node == null) {
            return null;
        }
        if(node.key == key) {
            return node;
        } else if(node.key < key) {
            return find(node.rightChild, key);
        } else {
            return find(node.leftChild, key);
        }
    }