Question

Distinct Count in Every Prefix

You are given an array of integers from 1 to 100000. For every index, print how many distinct values have appeared so far.

Input

The first line contains KaTeX can only parse string typed expression. The second line contains KaTeX can only parse string typed expression integers.

Output

Print the distinct count after every element.

Example

Example:
Input

6

2 2 5 2 7 5

Output

1 1 2 2 3 3

Online