Read problem statements in [Hindi], [Bengali], [Mandarin Chinese], [Russian], and [Vietnamese] as well.

Vivek likes playing with lasers, but his friend Divyansh says that reading biographies is much more interesting. In order to prove that lasers are fun too, Vivek proposed an interesting task involving them:

You are given $N$ points in a plane (numbered $1$ through $N$); for each valid $i$, the $i$-th point is $P_{i} = (i, A_{i})$. There are $N-1$ line segments between them (numbered $1$ through $N-1$); for each valid $i$, the $i$-th line segment is formed by connecting the points $P_{i}$ and $P_{i+1}$.

You should answer $Q$ queries. In each query, a laser beam is fired horizontally to the right, from a point $(x_{1}, y)$ to a point $(x_{2}, y)$ (where it stops and does not propagate further). Find the number of line segments it collides with on the way.

The beam is considered to collide with a line segment if it intersects or touches this segment, except when the left endpoint of this segment is $(x_{2}, y)$ or its right endpoint is $(x_{1}, y)$.

------ 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 $Q$.
The second line contains $N$ space-separated integers $A_{1}, A_{2}, \ldots, A_{N}$.
Each of the next $Q$ lines contains three space-separated integers $x_{1}$, $x_{2}$ and $y$ describing a query.

------ Output ------
For each query, print a single line containing one integer ― the number of line segments the beam collides with.

------ Constraints ------
$1 ≤ T ≤ 5$
$2 ≤ N ≤ 100,000$
$1 ≤ Q ≤ 100,000$
$1 ≤ A_{i} ≤ 10^{9}$ for each valid $i$
$1 ≤ x_{1} < x_{2} ≤ N$
$1 ≤ y ≤ 10^{9}$

------ Subtasks ------
Subtask #1 (30 points): $N, Q ≤ 2,000$

Subtask #2 (70 points): original constraints

----- Sample Input 1 ------
1

4 3

1 3 5 1

2 4 4

1 2 3

1 4 1
----- Sample Output 1 ------
2

1

2
----- explanation 1 ------
Example case 1:
- For the first query, the beam collides with the $2$-nd line segment and the $3$-rd line segment.
- For the second query, the beam collides only with the $1$-st line segment. We do not consider it to collide with the second line segment, since its left endpoint is $(x_{2},y)$.
- For the third query, the beam collides with the $1$-st line segment and the $3$-rd line segment.

见题面

见题面