G. Cyclic Buffer
time limit per test
2 s
memory limit per test
256 MB
input
standard input
output
standard output

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 \gt 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 \lt 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?

Input

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$$$.

Output

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.

Example
Input
2
5 3
2 4 3 5 1
1 1
1
Output
3
0
Note

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.