给定一个长度为 $$$n$$$ 的数组 $$$a$$$ 和一个数字 $$$k$$$。
子数组定义为数组的一个或多个连续元素的序列。您需要将数组 $$$a$$$ 拆分为 $$$k$$$ 不重叠的子数组 $$$b_1, b_2, \dots, b_k$$$ ,以便这些子数组的并集等于整个数组。此外,您需要最大化 $$$x$$$ 的值,该值等于 $$$i \in [1..k]$$$ 的最小值 MEX$$$(b_i)$$$。
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)$$$ — 数组的元素。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2\cdot 10^5$$$。
输出
对于每个查询,输出一个数字 - 最大值 $$$x$$$,使得存在将数组 $$$a$$$ 划分为 $$$k$$$ 子数组,其中最小 MEX 等于 $$$x$$$。
示例
输入复制
71 105 10 1 3 2 46 22 1 0 0 1 25 50 0 0 0 05 22 3 4 5 66 20 0 1 1 2 24 41 0 0 0
输出复制
1 5 3 1 0 1 0