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

Input

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

Output

For each test case, output $$$q$$$ integers, where the $$$i$$$-th integer represents the answer to the $$$i$$$-th query.

Note

In the first example test case:

For the second query, the subarray is $$$[1,2]$$$. You can take $$$c=[\min(1),\min(1,2)]=[1,1]$$$, which has $$$0$$$ inversions. It can be shown that it is the maximum number of inversions you can get over all beautiful arrays.

In the fourth example test case:

For the third query, the subarray is $$$[3,6,4,9]$$$. You can take $$$c=[\max(3),\max(3,6),\min(3,6,4),\min(3,6,4,9)]=[3,6,3,3]$$$, which will give a total of $$$2$$$ inversions. It can be shown that it is the maximum number of inversions you can get over all beautiful arrays.

A Simple Problem

Examples