Problem Description

Mr. Malnar has a topographic map that shows the elevation at each position in a certain area. Specifically, there are $n$ positions arranged in a line, and the $i$-th position is $h_i$ meters above sea level.

Sea level may rise. You are given $q$ queries. For the $i$-th query, you need to answer: if sea level rises by $x_i$ meters, how many islands will form in the interval $[l_i, r_i]$? An island is defined as a maximal segment in which every position has height greater than $x_i$.

The figure above shows the first query of Sample 1 and the second query of Sample 2, respectively. In the left figure, there are two islands $[2,2]$ and $[4,5]$ in the interval $[2,5]$, while in the right figure there are four islands $[1,1]$, $[4,4]$, $[8,8]$, and $[10,10]$.

Input Format

The first line contains two integers $n, q$.

The second line contains $n$ integers $h_{1\sim n}$, representing the initial elevation of each position.

The next $q$ lines each contain $3$ integers $l_i, r_i, x_i$, representing one query.

Output Format

Output $q$ lines. The $i$-th line contains one integer, the answer to the $i$-th query.

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

Hint

Constraints

For all testdata, $1\le n, q\le 2\times 10^5$, $0\le h_i, x_i\le 10^9$, $1\le l_i\le r_i\le n$.

Translated by ChatGPT 5