Yet Another MEX Problem

Key observation

The operation sounds scarier than it is. Classic Codeforces move: wrap a simple invariant in enough words to make your brain file a complaint.

After all deletions, exactly $k-1$ elements remain. So immediately:

$$\operatorname{mex}(\text{final}) \le k-1$$

because having MEX $k$ would require the final array to contain all $k$ values $0,1,\ldots,k-1$, which needs at least $k$ elements.

Also, deletions do not create values. So if we want final MEX at least $x$, the original array must contain every value:

$$0,1,2,\ldots,x-1.$$

This gives an upper bound: the answer is at most the MEX of the whole original array, and at most $k-1$.

So:

$$\text{answer} \le \min(k-1, \operatorname{mex}(a)).$$

Now we need to prove this bound is actually achievable.

Why the deletion rule does not hurt us

Suppose we want to preserve some target subsequence of exactly $k-1$ elements. We are allowed to choose which actual occurrences to preserve.

During the process, while the current array length is at least $k$, the operation selects some maximum-MEX window of length $k$. We do not control which maximum window exists, but we are allowed to pick any of them, and after choosing one, we may delete any element inside that window.

Here is the important invariant:

As long as the target subsequence has size $k-1$, no length-$k$ window can consist only of target elements.

That is just counting. A window has $k$ elements, but there are only $k-1$ protected elements total. So every length-$k$ window contains at least one unprotected element.

Therefore, whenever the operation forces us to delete from a maximum-MEX window, that window contains some disposable element. Delete that one. The protected elements survive.

Repeat until only $k-1$ elements remain. Since we never deleted protected elements, the remaining array is exactly our chosen target subsequence.

So yes: any subsequence of length $k-1$ can be made the final array. The maximum-MEX-window rule looks dangerous, but it cannot trap us. It is all bark, no bite.

Choosing the best target subsequence

Let

$$m = \min(k-1, \operatorname{mex}(a)).$$

By definition of $\operatorname{mex}(a)$, every value $0,1,\ldots,m-1$ appears in the original array.

Pick one occurrence of each of those $m$ values. That gives us $m$ protected elements. Since $m \le k-1$, we can add any other arbitrary elements until the protected set has exactly $k-1$ positions.

By the argument above, we can preserve those $k-1$ elements until the end. The final array contains all values $0,1,\ldots,m-1$, so its MEX is at least $m$.

The upper bound already said the answer cannot exceed $m$, so the answer is exactly:

$$\boxed{\min(k-1, \operatorname{mex}(a))}$$

Algorithm

For each test case:

1. Mark which values appear in the array.
2. Compute the MEX of the entire array.
3. Print $\min(k-1, \text{mex})$.

Values satisfy $0 \le a_i \le n$, so checking presence up to $n+1$ is enough.

Complexity

For each test case, the work is $O(n)$.

Across all test cases, this is:

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

which is easily fine for $2 \cdot 10^5$.