For an array (b) of length (m), define (f(b)) as follows: An array (c) of length (m) is considered beautiful if and only if for each (1 \le i \le m), (c_i) either equals (\max(b_1,b_2,\ldots,b_i)) or (\min(b_1,b_2,\ldots,b_i)). Then, (f(b)) is defined as the maximum number of inversions(^{\text{∗}}) over all beautiful arrays. You are given a permutation(^{\text{†}}) (p) of length (n). You need to answer (q) queries, where each query contains two integers (l) and (r) ((1 \le l \le r \le n)). For each query, please compute (f(p_l,p_{l+1},\ldots,p_{r})). (^{\text{∗}})The number of inversions of an array (a) of length (n) is defined as the number of pairs of integers ((i,j)) such that (1 \le i \lt j \le n) and (a_i \gt a_j). (^{\text{†}})A permutation of length (n) is an array consisting of (n) distinct integers from (1) to (n) in arbitrary order. For example, (2,3,1,5,4) is a permutation, but (1,2,2) is not a permutation ((2) appears twice in the array), and (1,3,4) is also not a permutation ((n=3) but there is (4) in the array). Each test contains multiple test cases. The first line contains the number of test cases (t) ((1 \le t \le 10^4)). The description of the test cases follows. The first line of each test case contains two integers (n) and (q) ((1 \le n,q \le 10^6)), representing the length of (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)), representing the permutation (p). Each of the next (q) lines contains two integers (l) and (r) ((1 \le l \le r \le n)), representing a query. It is guaranteed that the sum of (n) and the sum of (q) over all test cases both do not exceed (10^6). For each test case, output (q) integers, where the (i)-th intege