You are given an array a of N non-negative integers a1,a2,…,aN (1≤N≤2⋅105,0≤ai≤N). In one operation, you can change any element of a
to any non-negative integer.
The mex of an array is the minimum non-negative integer that it does not contain. For each i in the range 0 to N inclusive, compute the minimum number of operations you need in order to make the mex of a equal i.
INPUT FORMAT (input arrives from the terminal / stdin):
The first line contains N.
The next line contains a1,a2,…,aN.
OUTPUT FORMAT (print output to the terminal / stdout):
For each i in the range 0 to N, output the minimum number of operations for i on a new line. Note that it is always possible to make the mex of a equal to any i in the range 0 to N.
SAMPLE INPUT:
4
2 2 2 0
SAMPLE OUTPUT:
1
0
3
1
2
- To make the mex of a equal to 0, we can change a4 to 3 (or any positive integer). In the resulting array, [2,2,2,3], 0 is the smallest non-negative integer that the array does not contain, so 0 is the mex of the array.
- To make the mex of a equal to 1, we don't need to make any changes since 1 is already the smallest non-negative integer that a=[2,2,2,0] does not contain.
- To make the mex of a equal to 2, we need to change the first three elements of a. For example, we can change a to be [3,1,1,0].
SCORING:
Inputs 2-6: N≤103
Inputs 7-11: No additional constraints.
Problem credits: Benjamin Qi
扫码领取USACO试题答案+详细解析
咨询一对一备赛规划
