← 返回题目列表

Codeforces · 2183/B

B. 又一个 MEX 问题

中文机器翻译题面 查看原题

给定一个长度为 $$$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$$$ 的窗口中,您选择的窗口具有最大值$$$\操作员名称{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) 被定义为集合 $$$c$$$ 中不出现的最小非负整数 $$$x$$$。

输入

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

输出

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

示例

输入
复制

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

注意

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