Flooding

It is winter, and it has never been colder. Mr. Malnar looks at his photos from his last cruise on the Adriatic and remembers unforgettable moments. On the TV in the background, the news reports the latest proposals for slowing sea level rise. Looking at his coastal photos, Mr. Malnar wonders what they would have looked like if the sea had risen by a certain amount. There are so many pictures and so many questions that he asks for your help.

We model the coast as a sequence of $n$ numbers $h_1, h_2, \dots, h_n$, where $h_i$ is the relief height at the $i$-th point. Mr. Malnar has $q$ queries. The $i$-th query asks: if the sea level rose by $x_i$ meters, how many islands would there be between the $l_i$-th and $r_i$-th points?

An island is a maximal interval in which every $h_i$ is strictly greater than the sea level. A maximal interval cannot be extended in either direction while keeping that condition. The sea level starts at $0$ meters.

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

The second line contains $n$ integers $h_1, h_2, \dots, h_n$ ($0 \le h_i \le 10^9$) that describe the relief of the coast.

Each of the next $q$ lines contains three integers $l_i$, $r_i$ and $x_i$ ($1 \le l_i \le r_i \le n$, $0 \le x_i \le 10^9$) that describe the $i$-th query.

Print $q$ lines. The $i$-th line contains the answer to the $i$-th query.

In the first query of the first sample, the islands are the intervals $[2, 2]$ and $[4, 5]$ (left image). The second query has one island, $[5, 5]$. The third query has no islands because everything is under water.

In the second sample, the first query has islands $[3, 5]$ and $[8, 9]$. The second query (right image) has islands $[1, 1]$, $[4, 4]$, $[8, 8]$ and $[10, 10]$. The third query has islands $[1, 1]$, $[3, 4]$ and $[8, 10]$.