← 返回题目列表

Codeforces · 2059/B

B. 阵列的成本

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

给定一个长度为 $$$n$$$ 的数组 $$$a$$$ 和一个偶数 $$$k$$$ ($$$2 \le k \le n$$$)。您需要将数组 $$$a$$$ 精确地拆分为 $$$k$$$ 非空子数组$$$^{\dagger}$$$,以便数组 $$$a$$$ 的每个元素都属于一个子数组。

接下来,所有具有偶数索引的子数组(第二个、第四个、$$$\ldots$$$、$$$k$$$-th)都连接成单个数组$$$b$$$。之后,$$$0$$$被添加到数组$$$b$$$的末尾。

数组 $$$b$$$ 的成本定义为满足 $$$b_i \neq i$$$ 的最小索引 $$$i$$$。例如,数组 $$$b = [1, 2, 4, 5, 0]$$$ 的成本为 $$$3$$$,因为 $$$b_1 = 1$$$、$$$b_2 = 2$$$ 和 $$$b_3 \neq 3$$$。确定通过将数组 $$$a$$$ 最佳划分为子数组可以获得的数组 $$$b$$$ 的最小成本。

$$$^{\dagger}$$$数组 $$$x$$$ 是数组 $$$y$$$ 的子数组,如果 $$$x$$$ 可以通过删除开头的几个(可能是零个或全部)元素和结尾的几个(可能是零个或全部)元素从 $$$y$$$ 获得。

输入

每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$2 \le k \le n \le 2 \cdot 10^5$$$, $$$k$$$ 是偶数) — 数组 $$$a$$$ 的长度和子数组的数量。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — 数组 $$$a$$$ 的元素。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,输出一个整数——可以获得的数组 $$$b$$$ 的最小成本。

示例

输入 #1

4
3 2
1 1 1
8 8
1 1 2 2 3 3 4 4
5 4
1 1 1 2 2
5 4
1 1 1000000000 2 2

输出 #1

2
5
2
1

注意

在第一个测试用例中,只有两种可能的分区:$$$[[1], [1, 1]]$$$ 和 $$$[[1, 1], [1]]$$$。无论哪种情况,$$$b_1 = 1$$$,并且 $$$b_2 \ne 2$$$,因此成本为 $$$2$$$。

在第二个测试用例中,只有一种可能的分区,其中 $$$b = [1, 2, 3, 4, 0]$$$,因此成本为 $$$5$$$ ($$$b_5 = 0 \ne 5$$$)。

在第三个测试用例中,以下分区有效:$$$[[1], [1, 1], [2], [2]]$$$。那么$$$b = [1, 1, 2, 0]$$$,成本为$$$2$$$。