题目描述

给定一个长度为 $n$ 的数组 $a$，以及一个整数 $k$。令 $f(l, r)$ 表示 $\operatorname{mex}(a_l,a_{l+1},\ldots,a_r)$ $^\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}$ 最大的窗口 $[l, r]$。如果有多个符合条件的区间 $[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$，两个可能的 $(l,r)$ 对为 $(1,3)$ 和 $(2,4)$（因为这两个窗口的 $\operatorname{mex}$ 都为 $3$，是所有长度为 $3$ 的窗口中最大的）。因此，你可以在下一个步骤中删除下标 $1,2,3,4$ 之中的任意一个。

经过 $n-k+1$ 次操作后，你会得到一个长度为 $k-1$ 的序列。你的目标是最大化剩余元素的 $\operatorname{mex}$。请输出可能获得的最大 $\operatorname{mex}$。

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

输入格式

每组测试包含多个测试用例。第一行为测试用例数 $t$（$1 \le t \le 10^4$）。每组测试的描述如下。

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

第二行为 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$0\leq a_i \leq n$）。

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

输出格式

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

说明/提示

在第一个测试用例中，我们可以选择区间 $[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$。

由 ChatGPT 5 翻译

样例

5
3 3
0 0 0
4 2
0 2 1 3
5 3
0 1 2 1 0
6 2
0 1 0 1 2 0
7 5
0 1 2 4 0 3 1

1
1
2
1
4