#PU1492. USACO 2025 February Contest, Bronze — Problem 2. Making Mexes

USACO 2025 February Contest, Bronze — Problem 2. Making Mexes

USACO 2025 February Contest, Bronze — Problem 2. Making Mexes

题目描述

You are given an array aa of NN non-negative integers a1,a2,…,aNa_1, a_2, \dots, a_N (1≤N≤2⋅105,0≤ai≤N1\le N\le 2\cdot 10^5, 0\le a_i\le N). In one operation, you can change any element of aa to any non-negative integer. The mex of an array is the minimum non-negative integer that it does not contain. For each ii in the range 00 to NN inclusive, compute the minimum number of operations you need in order to make the mex of aa equal ii.

输入格式

The first line contains NN. The next line contains a1,a2,…,aNa_1,a_2,\dots, a_N.

输出格式

For each ii in the range 00 to NN, output the minimum number of operations for ii on a new line. Note that it is always possible to make the mex of aa equal to any ii in the range 00 to NN.

数据范围

Inputs 2-6: N≤103N\le 10^3 Inputs 7-11: No additional constraints. Problem credits: Benjamin Qi

样例

样例 1

4
2 2 2 0
1
0
3
1
2
To make the mex of $a$ equal to $0$, we can change $a_4$ 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]$.