2183B Yet Another MEX Problem

题目描述

给你一个长度为 $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$ 的窗口，使得在所有大小为 $k$ 的窗口中，你选的这个窗口的 $\operatorname{mex}$ 最大。如果有多个 $[l,r]$，你可以任选其一。然后，你必须选一个整数 $i$，满足 $l \leq i \leq r$，并从 $a$ 中删除 $a_i$。也就是说，新的序列变成 $[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$ 的最小未出现非负整数（MEX）定义为：最小的非负整数 $x$，它不在集合 $c$ 中出现。

输入格式

每个测试包含多个测试用例。第一行给出测试用例数量 $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$。

输出格式

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

说明

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

输入输出样例 #1

输入 #1

1
2
3
4
5
6
7
8
9
10
115
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
3
4
51
1
2
1
4