Given an array A=(a₁,a₂,…,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₁,a₂,…,a_m):

Select an interval [i,j] where 1≤i≤j≤m, and cyclically shift all elements of a_i,a_i+1,…,a_j−1,a_j in either direction, so that they become a_j,a_i,a_i+1,…,a_j−1 or a_i+1,…,a_j−1,a_j,a_i. 

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₁,p₂,…,p_n) of length n and you need to answer q independent queries of the following form:

In the i-th query, you are given parameters 1≤l_i≤r_i≤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[li,ri]=(pl_i,pl_i+1,…,pr_i). 
题目大意：给定任何一个长度为 m 的数组A= (a1, a2, . . . , am),令B(A)表示对A进行一次bubble sort循环之后得到的数组。令num(A)表示从A到B(A)最少需要移动元素(数组区间循环移位)的次数。给定一个1 − n的排列Pn以及q组查询。1 ≤ li ≤ ri ≤ n，求num(B[li, ri])。

The first line contains an integer T(1≤T≤10) denote the number of test cases.
For each test case, the first line contains two integers n,q (1≤n,q≤105), denoting the length of permutation P and the number of queries, respectively.
The second line contains n distinct integers p1,p2,…,pn (1≤pi≤n).
Each of the following q lines contains two integers li,ri (1≤li≤ri≤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.

hdu 7235 算法 倍增