CF2059B Cost of the Array

给定一个数组 $a$ 和一个**偶**整数 $k$ （ $2\le k\le n$ ）。你需要将数组 $a$ 分割为恰好 $k$ 个非空子数组。使得数组 $a$ 的每一个元素恰好属于其中一个子数组。 下一步，将所有具有偶数索引的子数组（第 $2$，$4$，…，$k$ 个）连接起来，成为一个新数组 $b$ 。之后，把 $0$ **添加**到数组 $b$ 的末尾。 数组 $b$ 的开销被定义为：最小的使 $b_i\ne i$ 的索引 $i$ 。比如，数组 $b=[1,2,4,5,0]$ 的开销为 $3$ ，因为 $b_1=1$ ， $b_2=2$ ，并且 $b_3\ne 3$。请确定一种划分数组 $a$ 的最优方案，使得数组 $b$ 的开销**最小**。 - 如果 $x$ 是数组 $y$ 的子数组，那么 $x$ 中的所有元素可以通过删除数组 $y$ 的开头几个元素（可能是零个或全部）和末尾几个元素（可能是零个或全部）得到。

**本题有多组测试数据。** 第一行输入一个正整数 $t$（$1\le t\le10^4$） 表示数据组数。每组测试数据的格式如下： 第一行输入两个整数 $n$ 和 $k$ （$2\le k\le n\le 2 \cdot 10^5$）， $k$ 是偶数。表示数组 $a$ 的长度和子数组数量。 第二行输入 $n$ 个整数 $a_1$ ，$a_2$ ， …， $a_n$ 。表示数组 $a$ 的元素。 保证所有测试数据中 $n$ 的和不超过 $2\cdot 10^5$ 。

对于每组测试数据，输出一行包含一个整数，表示数组 $b$ 的最小开销。

样例的第一组数据，只有两种可能的划分：$[[1],[1,1]]$ 和 $[[1,1],[1]]$ 。这两种情况都是 $b_1=1$ 并且 $b_2 \ne 1$ ，所以开销是 $2$ 。 样例的第二组数据，只有一种划分方法，其中 $b=[1,2,3,4,0]$ 。所以开销是 $5$ （$b_5=0 \ne 5$）。 样例的第三组数据，一种划分方案：$[[1],[1,1],[2],[2]]$ 。此时 $b=[1,1,2,0]$。这时开销是 $2$ 。