← 返回题目列表

Codeforces · 2093/E

E. 最小最大 MEX

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

给定一个长度为 $$$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$$$。

示例

输入
复制

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