Inversion

You have a sequence $\{a_1,a_2,...,a_n\}$ and you can delete a contiguous subsequence of length $m$. So what is the minimum number of inversions after the deletion.

There are multiple test cases. The first line of input contains an integer $T$, indicating the number of test cases. For each test case:

The first line contains two integers $n, m (1 \le n \le 10^5, 1 \le m < n)$ - the length of the seuqence. The second line contains $n$ integers $a_1,a_2,...,a_n (1 \le a_i \le n)$.

The sum of $n$ in the test cases will not exceed $2 \times 10^6$.

For each test case, output the minimum number of inversions.

2
3 1
1 2 3
4 2
4 1 3 2

0
1

BestCoder Round #58 (div.2)