P9662 [ICPC 2021 Macao R] Cyclic Buffer

有一个大小为 $n$ 的循环缓冲区，读入流从第 $1$ 个位置到第 $k$ 个位置（两者都包含在内）。设 $a_i$ ($1 \le i \le n$) 是缓冲区初始时第 $i$ 个位置上的整数。此外，$a_1, a_2, \cdots, a_n$ 形成 $n$ 的一个排列。 我们将以递增顺序访问从 $1$ 到 $n$ 的所有整数（两者都包含在内）。只有当整数位于具有读入流的位置（即位于前 $k$ 个位置）时，才能访问整数。如果某个整数无法访问，则可以将整个缓冲区向任意方向移动任意次数。 - 如果我们向左移动缓冲区一次，则位于第 $i$ 个位置的整数将移动到第 $(i - 1)$ 个位置（如果 $i > 1$），并且位于第 $1$ 个位置的整数将移动到第 $n$ 个位置。 - 如果我们向右移动缓冲区一次，则位于第 $i$ 个位置的整数将移动到第 $(i + 1)$ 个位置（如果 $i < n$），并且位于第 $n$ 个位置的整数将移动到第 $1$ 个位置。 我们需要移动缓冲区的最小次数，以便以递增顺序访问所有整数。

每个测试文件中包含多个测试用例。输入的第一行包含一个整数 $T$，表示测试用例的数量。对于每个测试用例： 第一行包含两个整数 $n$ 和 $k$ ($1 \le k \le n \le 10^6$)，表示缓冲区的大小和读入流的数量。 第二行包含 $n$ 个整数 $a_1, a_2, \cdots, a_n$ ($1 \le a_i \le n$)，其中 $a_i$ 表示缓冲区初始时第 $i$ 个位置上的整数。 保证给定的 $n$ 个整数构成 $n$ 的一个排列。还保证所有测试用例中 $n$ 的总和不超过 $10^6$。

对于每个测试用例，输出一行，包含一个整数，表示移动缓冲区的最小次数，以便所有整数可以以递增顺序访问。 **【样例解释】** 对于第一个样例测试用例： - 向右移动一次，使缓冲区变为 $\{1, 2, 4, 3, 5\}$。现在 $1$ 和 $2$ 可以按顺序访问，因为它们位于前 $3$ 个位置。 - 向左移动两次，使缓冲区变为 $\{4, 3, 5, 1, 2\}$。现在 $3$、$4$ 和 $5$ 可以按顺序访问，因为它们位于前 $3$ 个位置。 翻译来自于：[ChatGPT](https://chatgpt.com/)

For the first sample test case: - Shift to the right once so the buffer becomes $\{1, 2, 4, 3, 5\}$. $1$ and $2$ can now be visited in order as they are in the first $3$ positions. - Shift to the left twice so the buffer becomes $\{4, 3, 5, 1, 2\}$. $3$, $4$ and $5$ can now be visited in order as they are in the first $3$ positions.