Problems
You are given an array a of N non-negative integers
a₁, a₂, …, aₙ (1 ≤ N ≤ 2⋅10⁵, 0 ≤ aᵢ ≤ N). In one operation, you can change any element of a to any non-negative integer. The mex of an array is defined as the minimum non-negative integer that does not appear in the array. For each integer i in the range 0 to N inclusive, compute the minimum number of operations needed so that the mex of a becomes i.
Input
The first line contains an integer N.
The next line contains N space-separated integers: a₁, a₂, …, aₙ.
Output
For each i in the range 0 to N (inclusive), output the minimum number of operations required on a new line. (It is always possible to achieve a mex equal to any i in the range.)
Subtask
| # | Score | Condition |
|---|---|---|
| #1 | 50 | |
| #2 | 50 | No additional constraints. |
Example
4
2 2 2 0
1
0
3
1
2
To make the mex of a equal to 0, one possible solution is to change a₄ to 3 (or any positive integer). In the resulting array [2, 2, 2, 3], 0 is the smallest non-negative integer that does not appear, so the mex is 0.
To make the mex equal to 1, no changes are needed because 1 is already the smallest non-negative integer missing from the array [2, 2, 2, 0].
To make the mex equal to 2, you can change the first three elements of a. For example, modifying a to [3, 1, 1, 0] results in a mex of 2.
You must sign in to write code.