In a country Stone Land, there are $N$ stones arranged in a row from left to right. Each stone has some height represented by a positive number. The stones are numbered from $1$ to $N$ from left to right.

You are given an array H of size $N$ consisting of the height of the $N$ stones from left to
right.

Stone at $j^{th}$ position is visible from the stone at $i^{th}$ position if:-
1. $j>i$
2. $max(H[i],H[i+1],H[i+2],....,H[j-1])$ $<$ $H[j]$

You are asked $M$ queries.
Each query consists of two different positions of stones $A$ and $B$.
You have to Print the total number of stones that are visible from both the stones at the position $A$ and $B$.

------ Input ------

The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first line of each test case contains two space-separated integers $N$ and $M$, where $N$ is the number of stones and $M$ is the number of queries.
The Second line consists of $N$ space-separated integers (array H) denoting the height of stones from left to the right separated by a space.
Next, $M$ lines consist of two space-separated integers $A$ and $B$ separated by space where $A$ and $B$ are positions of stones.

------ Constraints ------
$1 ≤ T ≤ 5$
$2 ≤ N ≤ 10^{5}$
$1 ≤ M ≤ 10^{5}$
$1 ≤ H[i] ≤ 10^{9}$, where H[i] denotes the height of $i^{th}$ stone, and $1 ≤ i ≤ N$
$1 ≤ A, B ≤ N$
It is guaranteed that the sum of $N$ over all test cases does not exceed $10^{5}$.
It is guaranteed that the sum of $M$ over all test cases does not exceed $10^{5}$.

------ Output ------
For each query, print the total number of stones that are visible from both the stones at the position $A$ and $B$ in a new line.

------ Example Input ------

1
6 6
3 10 20 20 5 50
1 2
2 4
4 3
4 5
1 3
4 4

------ Example Output ------

2
1
1
1
1
1

------ Explanation ------

Query $1$: Stone at position $1$ can see the stones at position $(2, 3, 6)$ whereas stone at position $2$ can see the stones at position $(3, 6)$. Thus, the total number of stones that are visible from both stones is $2$.

见题面

见题面