MEX Count

For each deletion count $k$, we need the number of distinct MEX values that can happen after deleting exactly $k$ elements.

The trap is trying to simulate deletions. Don't. That's a combinatorial swamp, and it smells bad.

Instead, fix the MEX value first.

When is MEX $m$ possible?

After deletions, having $\mathrm{MEX}=m$ means:

• every value $0,1,\dots,m-1$ is still present at least once;
• value $m$ is completely absent.

So two things matter:

1. All values below $m$ must exist in the original array.
2. We must delete all copies of $m$.

Let $\text{cnt}[x]$ be the frequency of value $x$.

The minimum deletions needed for MEX $m$ is clearly:

$$\text{cnt}[m]$$

because every copy of $m$ has to disappear.

Now, what is the maximum number of deletions?

We must keep at least one copy of each value $0,1,\dots,m-1$. That's $m$ elements that must remain. Everything else can be deleted.

So the maximum deletions is:

$$n-m$$

Therefore, if all values below $m$ exist, MEX $m$ is possible for exactly these deletion counts:

$$\text{cnt}[m] \le k \le n-m$$

provided the interval is not empty.

Why every value inside the interval works

After deleting all copies of $m$, we may still need to delete more elements.

The optional deletions can come from:

• duplicate copies of values below $m$, while keeping one of each;
• any values greater than $m$.

The total number of optional removable elements is exactly:

$$n - m - \text{cnt}[m]$$

So we can delete any extra amount from $0$ up to that number. No weird gaps. No hidden parity nonsense. Just a clean interval.

Counting intervals

Now each valid MEX $m$ contributes $1$ to every answer $ans[k]$ where:

$$\text{cnt}[m] \le k \le n-m$$

This screams difference array.

For each valid $m$:

• diff[cnt[m]]++
• diff[n - m + 1]--

Then prefix-sum diff to get all answers.

Which $m$ values do we check?

We scan $m=0$ to $n$ while keeping whether all smaller values have appeared.

For $m=0$, the condition is vacuously true.

After processing $m$, if $\text{cnt}[m]=0$, then any larger MEX becomes impossible, because that larger MEX would require $m$ to be present. So the scan can stop after that missing value.

Complexity per test case:

$$O(n)$$

Total complexity over all tests:

$$O\left(\sum n\right)$$

which is easily fine.