CF2183B.Yet Another MEX Problem

You are given an array $a$ of length $n$, and an integer $k$. Let $f(l,r)$ be the value of $\operatorname{mex}(a_l,a_{l+1},\ldots,a_r)$$^{\text{∗}}$. You want to perform the following operation $n-k+1$ times:

• Let the current length of the sequence be $|a|$. You need to find an interval $[l, r]$ of length $k$ such that $\operatorname{max}_{i=1}^{|a|-k+1} f(i, i+k-1) = f(l, r).$ In other words, you need to select a window of size $k$ such that among all windows of size $k$, the window you selected has the maximum $\operatorname{mex}$. If multiple $[l,r]$ exist, you may select any. Then, you must select any integer $i$ such that $l \leq i \leq r$, and delete $a_i$ from $a$. That is, your new sequence will be $[a_1, a_2, \ldots, a_{i-1}, a_{i+1}, a_{i+2}, \ldots, a_n]$.

For example, in the array $[1,2,0,1,3,0]$ with $k=3$, the two possible $(l,r)$ pairs are $(1,3)$ and $(2,4)$ (since they each have $\operatorname{mex} 3$, which is the maximum among all windows of size $3$). Therefore, you can remove any one of the indices $1,2,3,4$ in your next move.

After $n - k + 1$ operations, you will have a sequence of length $k-1$. Your objective is to maximize the $\operatorname{mex}$ of the remaining elements. Please output the maximum $\operatorname{mex}$ possible.

$^{\text{∗}}$The minimum excluded (MEX) of a collection of integers $c_1, c_2, \ldots, c_k$ is defined as the smallest non-negative integer $x$ which does not occur in the collection $c$.

给你一个长度为 $n$ 的数组 $a$ 和一个整数 $k$。定义 $f(l,r)$ 为子数组 $a_l,a_{l+1},\ldots,a_r$ 的 $\operatorname{mex}$ 值$^{\text{∗}}$。你需要执行以下操作 $n-k+1$ 次：

• 设当前序列长度为 $|a|$。你需要找出一个长度为 $k$ 的区间 $[l, r]$，使得

  $$\operatorname{max}_{i=1}^{|a|-k+1} f(i, i+k-1) = f(l, r).$$

  换言之，你需要选择一个大小为 $k$ 的滑动窗口，使其 $\operatorname{mex}$ 在所有大小为 $k$ 的窗口中达到最大。若存在多个满足条件的 $[l,r]$，任选其一即可。接着，你必须任选一个下标 $i$ 满足 $l \leq i \leq r$，并将 $a_i$ 从 $a$ 中删除。即新序列为 $[a_1, a_2, \ldots, a_{i-1}, a_{i+1}, a_{i+2}, \ldots, a_n]$。

例如，在数组 $[1,2,0,1,3,0]$ 中取 $k=3$，所有长度为 $3$ 的窗口中，$(l,r) = (1,3)$ 和 $(2,4)$ 对应的 $\operatorname{mex}$ 均为 $3$（这是所有长度为 $3$ 的窗口中 $\operatorname{mex}$ 的最大值）。因此，下一步你可以删除下标 $1,2,3$ 或 $4$ 中的任意一个元素。

经过 $n - k + 1$ 次操作后，剩余序列的长度将为 $k-1$。你的目标是使剩余元素的 $\operatorname{mex}$ 尽可能大。请输出所能达到的最大 $\operatorname{mex}$ 值。

$^{\text{∗}}$ 一组整数 $c_1, c_2, \ldots, c_k$ 的最小未出现值（MEX） 定义为未在该集合中出现的最小非负整数 $x$。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains two positive integers $n$ and $k$ ($2 \le k \le n \le 2 \cdot 10^5$).

The second line of each test case contains $n$ integers $a_1,a_2,\ldots,a_n$ ($0 \le a_i \le n$).

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。随后是各测试用例的描述。

每个测试用例的第一行包含两个正整数 $n$ 和 $k$（$2 \le k \le n \le 2 \cdot 10^5$）。

每个测试用例的第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$（$0 \le a_i \le n$）。

保证所有测试用例的 $n$ 值之和不超过 $2 \cdot 10^5$。

Output a single non-negative integer representing your answer.

输出一个表示答案的非负整数。

In the first test case, we can select the interval $[1,3]$. Then, delete $a_2$ to obtain $[0,0]$. The process terminates, and the $\operatorname{mex}$ of the remaining elements is $1$.

In the third test case, we can perform the following operations:

• Select $i=1,j=3$. This is allowed because the $\operatorname{mex}$ of all windows of size $3$ is $3,0,3$, and the window $[1,3]$ has a $\operatorname{mex}$ of $3$, which is the largest. Then, remove $a_2$. The sequence is now $[0,2,1,0]$.
• Select $i=2,j=4$. Then, remove $a_2$. The sequence is now $[0,1,0]$.
• Select $i=1,j=3$. Then, remove $a_1$. The sequence is now $[1,0]$. The process terminates, and the final $\operatorname{mex}$ is $2$.

在第一个测试用例中，我们可以选择区间 $[1,3]$。然后删除 $a_2$，得到 $[0,0]$。该过程终止，剩余元素的 $\operatorname{mex}$ 为 $1$。

在第三个测试用例中，我们可以执行以下操作：

• 选择 $i=1,j=3$。这是允许的，因为所有长度为 $3$ 的滑动窗口的 $\operatorname{mex}$ 值分别为 $3,0,3$，而窗口 $[1,3]$ 的 $\operatorname{mex}$ 为 $3$，是其中最大的。随后删除 $a_2$，序列变为 $[0,2,1,0]$。
• 选择 $i=2,j=4$。然后删除 $a_2$，序列变为 $[0,1,0]$。
• 选择 $i=1,j=3$。然后删除 $a_1$，序列变为 $[1,0]$。该过程终止，最终的 $\operatorname{mex}$ 为 $2$。