Minimum Operations for Target MEX

You are given an array a of N non‐negative integers: a[1], a[2], …, a[N] (with 1 ≤ N ≤ 2×105 and 0 ≤ a[i] ≤ N for every i). In one operation you can change any element of the array to any non‐negative integer.

Define the mex of an array as the smallest non‐negative integer that does not appear in it. For every i from 0 to N you are to compute the minimum number of operations needed so that the mex of the array becomes i.

More formally, for every integer i in the range \(0 \le i \le N\), you must modify the array so that:

• For every integer \(0 \le j \lt i\), the number \(j\) appears at least once in the array.
• The integer \(i\) does not appear in the array.

It can be shown that if it is impossible to achieve a given target mex, then the answer is -1.

Note on Operations: When fixing the array to achieve a target mex, note that you do not need to remove extra copies of numbers less than i (duplicates do not affect the mex property) but you must ensure that each number in \(0,1,\dots,i-1\) appears at least once, and that no element equals i. This means that if a number in \(0,1,\dots,i-1\) is missing, you can convert an element (even one that is originally equal to i) to that missing number, with one operation per conversion. Also, every element that is originally equal to i must be modified unless it is used to fill a missing number.

The answer for a target mex i is thus given by:

[ \text{answer}(i)=\begin{cases} ,; ;; ; ;;; ; ; ;; freq(0) & \text{if } i=0,\[1mm] \max\Big(freq(i),; missing\Big) & \text{if } i\ge 1 \text{ and if } pool \ge missing,\[1mm] -1 & \text{if } pool < missing, \end{cases} ]

where for i ≥ 1:

• freq(x) is the number of times x occurs in the array.
• missing is the count of numbers in \(\{0, 1, \dots, i-1\}\) that do not appear in the array (i.e. for which freq(j)==0).
• pool is defined as \(\displaystyle \sum_{j=0}^{i-1}\max(0, freq(j)-1) + freq(i)\), which represents the total number of elements available for conversion to cover missing numbers.

Print the answers for i = 0, 1, …, N as a sequence of N+1 space‐separated integers.

inputFormat

The first line contains a single integer N (1 ≤ N ≤ 2×105).

The second line contains N space‐separated integers representing the array a (0 ≤ a[i] ≤ N).

outputFormat

Print N+1 space‐separated integers, where the i-th integer is the minimum number of operations required so that the mex of the array becomes i. If it is impossible, print -1 for that i.

sample

4
0 2 1 0

2 1 1 0 1

</p>