CF1768B.Quick Sort

You are given a permutation$^\dagger$ $p$ of length $n$ and a positive integer $k \le n$.

In one operation, you:

• Choose $k$ distinct elements $p_{i_1}, p_{i_2}, \ldots, p_{i_k}$.
• Remove them and then add them sorted in increasing order to the end of the permutation.

For example, if $p = [2,5,1,3,4]$ and $k = 2$ and you choose $5$ and $3$ as the elements for the operation, then $[2, \color{red}{5}, 1, \color{red}{3}, 4] \rightarrow [2, 1, 4, \color{red}{3},\color{red}{5}]$.

Find the minimum number of operations needed to sort the permutation in increasing order. It can be proven that it is always possible to do so.

$^\dagger$ A permutation of length $n$ is an array consisting of $n$ distinct integers from $1$ to $n$ in arbitrary order. For example, $[2,3,1,5,4]$ is a permutation, but $[1,2,2]$ is not a permutation ($2$ appears twice in the array), and $[1,3,4]$ is also not a permutation ($n=3$ but there is $4$ in the array).

给你一个长度为 $n$ 的排列$^\dagger$ $p$ 和一个正整数 $k \le n$。

每次操作中，你需要：

• 选择 $k$ 个互不相同的元素 $p_{i_1}, p_{i_2}, \ldots, p_{i_k}$；
• 将它们从排列中移除，然后将它们按升序排序后添加到排列末尾。

例如，若 $p = [2,5,1,3,4]$ 且 $k = 2$，你选择的元素为 $5$ 和 $3$，则操作过程为：
$[2, \color{red}{5}, 1, \color{red}{3}, 4] \rightarrow [2, 1, 4, \color{red}{3},\color{red}{5}]$。

求使该排列变为升序排列所需的最少操作次数。可以证明，总能通过有限次操作实现升序排列。

$^\dagger$ 长度为 $n$ 的排列是指由 $1$ 到 $n$ 中 $n$ 个互不相同的整数以任意顺序组成的数组。例如，$[2,3,1,5,4]$ 是一个排列，但 $[1,2,2]$ 不是排列（数字 $2$ 出现了两次），$[1,3,4]$ 也不是排列（此时 $n=3$，但数组中出现了 $4$）。

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

The first line of each test case contains two integers $n$ and $k$ ($2 \le n \le 10^5$, $1 \le k \le n$).

The second line of each test case contains $n$ integers $p_1,p_2,\ldots, p_n$ ($1 \le p_i \le n$). It is guaranteed that $p$ is a permutation.

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

第一行包含一个整数 $t$（$1 \le t \le 10^4$）—— 表示测试用例的数量。随后是各测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $k$（$2 \le n \le 10^5$，$1 \le k \le n$）。

每个测试用例的第二行包含 $n$ 个整数 $p_1,p_2,\ldots, p_n$（$1 \le p_i \le n$）。保证 $p$ 是一个排列。

保证所有测试用例的 $n$ 之和不超过 $10^5$。

For each test case output a single integer — the minimum number of operations needed to sort the permutation. It can be proven that it is always possible to do so.

对于每个测试用例，输出一个整数——即排序该排列所需的最少操作次数。可以证明，这总是可行的。

In the first test case, the permutation is already sorted.

In the second test case, you can choose element $3$, and the permutation will become sorted as follows: $[\color{red}{3}, 1, 2] \rightarrow [1, 2, \color{red}{3}]$.

In the third test case, you can choose elements $3$ and $4$, and the permutation will become sorted as follows: $[1, \color{red}{3}, 2, \color{red}{4}] \rightarrow [1, 2, \color{red}{3},\color{red}{4}]$.

In the fourth test case, it can be shown that it is impossible to sort the permutation in $1$ operation. However, if you choose elements $2$ and $1$ in the first operation, and choose elements $3$ and $4$ in the second operation, the permutation will become sorted as follows: $[\color{red}{2}, 3, \color{red}{1}, 4] \rightarrow [\color{blue}{3}, \color{blue}{4}, \color{red}{1}, \color{red}{2}] \rightarrow [1,2, \color{blue}{3}, \color{blue}{4}]$.

在第一个测试用例中，排列已经有序。

在第二个测试用例中，你可以选择元素 $3$，排列将按如下方式变为有序：$[\color{red}{3}, 1, 2] \rightarrow [1, 2, \color{red}{3}]$。

在第三个测试用例中，你可以选择元素 $3$ 和 $4$，排列将按如下方式变为有序：$[1, \color{red}{3}, 2, \color{red}{4}] \rightarrow [1, 2, \color{red}{3},\color{red}{4}]$。

在第四个测试用例中，可以证明无法通过 $1$ 次操作将排列排序。然而，若在第一次操作中选择元素 $2$ 和 $1$，并在第二次操作中选择元素 $3$ 和 $4$，则排列将按如下方式变为有序：$[\color{red}{2}, 3, \color{red}{1}, 4] \rightarrow [\color{blue}{3}, \color{blue}{4}, \color{red}{1}, \color{red}{2}] \rightarrow [1,2, \color{blue}{3}, \color{blue}{4}]$。