Zatopljenje

문제

It’s winter, it has never been colder, and Mr. Malnar is looking at his photos from his last cruise on the Adriatic and recalls unforgettable moments. The TV is on in the background, broadcasting news about the latest proposals for measures to slow down sea level rise. Looking at his photos of the coast, Mr. Malnar asks himself what the photos would have looked like if sea level had risen a certain amount. There are so many pictures, and even more questions, so Mr. Malnar asks for your help.

We imagine the coast as a sequence of $nn$ numbers $h_1,h_2,\dots ,h_{n}h\_1,\; h\_2,\; \backslash dots\; ,\; h\_n$, where the $ii$-th number represents relief height at the $ii$-th point. Mr. Malnar has $qq$ queries, where the $ii$-th query is as following: How many islands would there be between the $l_{i}l\_i$-th and $r_{i}r\_i$-th point if the sea level rose by $x_{i}x\_i$ meters?

The left image shows the first query of the first sample test case, and the right image shows the second query of the second sample test case.

The left islands correspond to intervals $[2,2][2,\; 2]$ and $[4,5][4,\; 5]$.

The right islands correspond to intervals $[1,1][1,\; 1]$, $[4,4][4,\; 4]$, $[8,8][8,\; 8]$ and $[10,10][10,\; 10]$.

An island is defined as the maximal interval where every $h_{i}h\_i$ is strictly greater than the sea level. A maximal interval is one that cannot be extended in either direction while keeping the mentioned condition true. Initially, the sea level is at $00$ meters.

입력

The first line contains integers $nn$ and $qq$ (1 ≤ n, q ≤ 2 \cdot 10^5), the length of the sequence and the number of queries.

The second line contains $nn$ integers $h_1,h_2,\dots ,h_{n}h\_1,\; h\_2,\; \backslash dots\; ,\; h\_n$ (0 ≤ h_i ≤ 10^9) that describe the relief of the coast.

In each of the next $qq$ lines there are three integers $l_{i}l\_i$, $r_{i}r\_i$ and $x_{i}x\_i$ (1 ≤ l_i ≤ r_i ≤ n, 0 ≤ x_i ≤ 10^9) that describe the $ii$-th query.

출력

In the $ii$-th of the $qq$ lines print the answer to the $ii$-th query. Each of the queries is independent of the others.

힌트

Clarification of the first example:

The first query is shown in the left image in the task description, islands correspond to intervals $[2,2][2,\; 2]$ and $[4,5][4,\; 5]$. In the second query island corresponds to interval $[5,5][5,\; 5]$. In the third query there are no islands because everything is under water.

Clarification of the second example: In the first query islands correspond to intervals $[3,5][3,\; 5]$ and $[8,9][8,\; 9]$. In the second query (shown in the right image in the task description) islands correspond to intervals $[1,1][1,\; 1]$, $[4,4][4,\; 4]$, $[8,8][8,\; 8]$ and $[10,10][10,\; 10]$, while in the third query islands correspond to intervals $[1,1][1,\; 1]$, $[3,4][3,\; 4]$ and $[8,10][8,\; 10]$.

6 3
2 4 2 3 4 1
2 5 2
3 5 3
3 4 4

2
1
0

10 3
5 0 3 4 2 0 1 6 3 5
3 9 1
1 10 3
1 10 2

2
4
3