You are given an array of n integers. For every prefix (the first element, the first two elements, and so on up to the whole array), report how many distinct values it contains.
Output the n counts in order, where the i-th count refers to the prefix ending at index i (0-indexed).
Input format
Line 1: an integer n.
Line 2: n space-separated integers, the array.
Output format
One line: n integers, space-separated, where the i-th is the number of distinct values among the first i + 1 elements.
Constraints
- 1 <= n <= 100000
- -1000000000 <= each value <= 1000000000