Luffy and Zoro are exploring a ruined island containing a row of $$$n$$$ ancient stone towers. The height of the tower at position $$$i$$$ is $$$a_i$$$.
For each query $$$[l,r]$$$, consider only the towers whose positions are between $$$l$$$ and $$$r$$$, inclusive. Towers outside this segment do not affect the query.
The destruction happens in rounds. In each round, a remaining tower at position $$$i$$$ crumbles if there exist two other remaining towers at positions $$$j$$$ and $$$k$$$ such that $$$l \le j \lt i \lt k \le r$$$ and $$$a_j \gt a_i$$$ and $$$a_k \gt a_i$$$.
In other words, a tower crumbles if there is at least one strictly taller remaining tower somewhere to its left and at least one strictly taller remaining tower somewhere to its right.
The towers at positions $$$j$$$ and $$$k$$$ do not need to be adjacent to the tower at position $$$i$$$. Any remaining towers on its left and right may satisfy the condition.
All towers satisfying the condition are removed simultaneously. The process is repeated until an entire round passes without any tower crumbling.
For each query, determine how many towers in the segment $$$[l,r]$$$ remain after the process ends.
The first line contains an integer $$$t$$$ ($$$1 \le t \le 10^{4}$$$) — the number of test cases.
The first line of each test case contains two integers $$$n$$$ and $$$q$$$ ($$$1 \le n, q \le 2 \times 10^{5}$$$) — the number of towers and the number of queries.
The second line contains $$$n$$$ distinct integers $$$a_{1}, a_{2}, \dots, a_{n}$$$ ($$$1 \le a_{i} \le 10^{9}$$$) — the heights of the towers.
Each of the next $$$q$$$ lines contains two integers $$$l$$$ and $$$r$$$ ($$$1 \le l \le r \le n$$$) — the segment for the query.
It is guaranteed that the sum of $$$n$$$ and the sum of $$$q$$$ over all test cases do not exceed $$$2 \times 10^{5}$$$.
For each query, output one integer — the number of towers that stay standing in the segment $$$[l, r]$$$.
15 24 1 3 2 51 52 5
23
For the first query, towers with heights 1, 3, and 2 disappear in the first round. The towers with heights 4 and 5 remain.
For the second query, only 2 is removed.
