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).
Line 1: an integer n.
Line 2: n space-separated integers, the array.
One line: n integers, space-separated, where the i-th is the number of distinct values among the first i + 1 elements.
Example 1
Input
5 1 2 2 3 1
Expected
1 2 2 3 3
Explanation
Prefixes: {1}->1, {1,2}->2, {1,2}->2, {1,2,3}->3, {1,2,3}->3. Output '1 2 2 3 3'.
Example 2
Input
3 7 7 7
Expected
1 1 1
Explanation
Every prefix contains only the value 7, so each distinct count is 1: '1 1 1'.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →