给定一个长度为 $$$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$$$。
输出
输出一个代表您答案的非负整数。
示例
输入复制
53 30 0 04 20 2 1 35 30 1 2 1 06 20 1 0 1 2 07 50 1 2 4 0 3 1
输出复制
11214
注意
在第一个测试用例中,我们可以选择区间$$$[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$$$。