[ICPC2021 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/)

There is a cyclic buffer of size $n$ with readers from the $1$-st position to the $k$-th position (both inclusive). Let $a_i$ ($1 \le i \le n$) be the integer at the $i$-th position of the buffer initially. What's more, $a_1, a_2, \cdots, a_n$ form a permutation of $n$. We're going to visit all the integers from $1$ to $n$ (both inclusive) in increasing order. An integer can be visited only when it is residing in positions with readers (that is to say, when it is in the first $k$ positions). In case that an integer cannot be visited, we can shift the whole buffer in either directions any number of times. - If we shift the buffer to the left once, integers in the $i$-th position will be moved to the $(i - 1)$-th position if $i > 1$, and integer in the $1$-st position will be moved to the $n$-th position. - If we shift the buffer to the right once, integers in the $i$-th position will be moved to the $(i + 1)$-th position if $i < n$, and integer in the $n$-th position will be moved to the $1$-st position. What's the minimum number of times to shift the buffer so that we can visit all the integers in increasing order?

There are multiple test cases. The first line of the input contains an integer $T$ indicating the number of test cases. For each test case: The first line contains two integers $n$ and $k$ ($1 \le k \le n \le 10^6$) indicating the size of the buffer and the number of readers. The second line contains $n$ integers $a_1, a_2, \cdots, a_n$ ($1 \le a_i \le n$) where $a_i$ indicates the integer in the $i$-th position of the buffer initially. It's guaranteed that the given $n$ integers form a permutation of $n$. It's also guaranteed that the sum of $n$ of all test cases will not exceed $10^6$.

For each test case output one line containing one integer indicating the minimum number of times to shift the buffer so that all integers can be visited in increasing order.

2
5 3
2 4 3 5 1
1 1
1

3
0

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.