You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

问题描述

给定一个长度为 $n$ 的数组 $a$ 和一个数字 $k$。

子数组定义为数组中连续的一个或多个元素的序列。你需要将数组 $a$ 分成 $k$ 个不重叠的子数组 $b_1, b_2, \dots, b_k$，使得这些子数组的并集等于整个数组。此外，你需要最大化 $x$ 的值，其中 $x$ 是所有子数组中最小的 MEX$(b_i)$ 的值，$i \in [1..k]$。

MEX$(v)$ 表示数组 $v$ 中最小的非负整数，该整数不在数组中。

输入

第一行包含一个整数 $t$ $(1 \leq t \leq 10^4)$ — 测试用例的数量。

每个测试用例的第一行包含两个整数 $n$, $k$ $(1 \leq k \leq n \leq 2 \cdot 10^5)$ — 数组的长度和将数组分割成的子数组数量。

每个测试用例的第二行包含 $n$ 个整数 $a_i$ $(0 \leq a_i \leq 10^9)$ — 数组的元素。

保证所有测试用例中，所有数组的元素数量总和不超过 $2 \cdot 10^5$。

输出

对于每个测试用例，输出一个整数 — 最大值 $x$，使得存在一种方式将数组 $a$ 分割成 $k$ 个子数组，并且这些子数组的最小 MEX 等于 $x$。

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

1
5
3
1
0
1
0