Fast Bubble Sort

Given an array $A=(a_1,a_2,\ldots,a_m)$ of length $m$, denote by array $B(A)$ the output of a single iteration of bubble sort with input array $A$, i.e., the output of the following algorithm with input array $A$.




You may perform the following operation any number (including zero) of times on the array $A=(a_1,a_2,\ldots,a_m)$:

<ol>
<li> Select an interval $[i,j]$ where $1\leq i\leq j\leq m$, and cyclically shift all elements of $a_i,a_{i+1},\dots,a_{j-1},a_j$ in either direction, so that they become $a_j,a_i,a_{i+1},\dots,a_{j-1}$ or $a_{i+1},\dots,a_{j-1},a_{j},a_{i}$. </li>
</ol>

For example, if we cyclically shift the interval $[1,4]$ of the array $A=[1,2,3,4,5]$ to the right, the resulting array would be $A'=[4,1,2,3,5]$.


You are now given a permutation $P=(p_1,p_2,\ldots,p_n)$ of length $n$ and you need to answer $q$ independent queries of the following form:

<ol>
<li> In the $i$-th query, you are given parameters $1 \le l_i \le r_i \le n$ and you are supposed to find the minimum number of above operations needed to transform the subarray $P[l_i,r_i]$ to $B(P[l_i,r_i])$, where $P[l_i,r_i]= (p_{l_i}, p_{l_i + 1}, \ldots, p_{r_i})$. </li>
</ol>

The first line contains an integer $T(1\leq T\leq 10)$ denote the number of test cases.

For each test case, the first line contains two integers $n,q$ ($1 \le n,q \le 10^5$), denoting the length of permutation $P$ and the number of queries, respectively.

The second line contains $n$ distinct integers $p_1,p_2,\ldots,p_n$ ($1 \le p_i \le n$).

Each of the following $q$ lines contains two integers $l_i, r_i$ ($1 \le l_i \le r_i \le n$), denoting the parameters for the $i$-th query.

For each query of each test case, output an integer in one line, denoting the answer.

1
10 5
3 7 9 2 6 4 5 8 10 1
1 10
2 6
7 9
4 9
3 3

2
1
0
1
0

2022“杭电杯”中国大学生算法设计超级联赛（9）