CF2059B.Cost of the Array

You are given an array $a$ of length $n$ and an even integer $k$ ($2 \le k \le n$). You need to split the array $a$ into exactly $k$ non-empty subarrays$^{\dagger}$ such that each element of the array $a$ belongs to exactly one subarray.

Next, all subarrays with even indices (second, fourth, $\ldots$, $k$-th) are concatenated into a single array $b$. After that, $0$ is added to the end of the array $b$.

The cost of the array $b$ is defined as the minimum index $i$ such that $b_i \neq i$. For example, the cost of the array $b = [1, 2, 4, 5, 0]$ is $3$, since $b_1 = 1$, $b_2 = 2$, and $b_3 \neq 3$. Determine the minimum cost of the array $b$ that can be obtained with an optimal partitioning of the array $a$ into subarrays.

$^{\dagger}$An array $x$ is a subarray of an array $y$ if $x$ can be obtained from $y$ by the deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end.

给你一个长度为 $n$ 的数组 $a$ 和一个偶数 $k$（$2 \le k \le n$）。你需要将数组 $a$ 恰好划分为 $k$ 个非空子数组$^{\dagger}$，使得数组 $a$ 中的每个元素恰好属于其中一个子数组。

接下来，将所有下标为偶数的子数组（即第 $2$ 个、第 $4$ 个、……、第 $k$ 个子数组）按顺序拼接成一个新数组 $b$。然后，在数组 $b$ 的末尾添加一个 $0$。

定义数组 $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$ 的一个子数组。

Each test consists of multiple test cases. The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains two integers $n$ and $k$ ($2 \le k \le n \le 2 \cdot 10^5$, $k$ is even) — the length of the array $a$ and the number of subarrays.

The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^9$) — the elements of the array $a$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

每个测试包含多个测试用例。第一行包含一个整数 $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$。

For each test case, output a single integer — the minimum cost of the array $b$ that can be obtained.

对于每个测试用例，输出一个整数——可得到的数组 $b$ 的最小代价。

In the first test case, there are only two possible partitionings: $[[1], [1, 1]]$ and $[[1, 1], [1]]$. In either case, $b_1 = 1$, and $b_2 \ne 2$, so the cost is $2$.

In the second test case, there is only one possible partitioning, where $b = [1, 2, 3, 4, 0]$, so the cost is $5$ ($b_5 = 0 \ne 5$).

In the third test case, the following partitioning works: $[[1], [1, 1], [2], [2]]$. Then $b = [1, 1, 2, 0]$, and the cost is $2$.

在第一个测试用例中，仅有两种可能的划分方式：$[[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$。