Island Counting

Mr. Malnar has a topographic map where each of the $n$ positions in a row has an altitude $h_i$ above sea level. The sea level may rise. You are given $q$ queries; for the $i$-th query, if the sea level rises by $x_i$ meters, determine how many islands are formed in the segment $[l_i, r_i]$. An island is defined as a maximal contiguous segment where every position has an altitude greater than $x_i$.

For example, consider the region shown in the left image: in the interval $[2,5]$, there are two islands: $[2,2]$ and $[4,5]$. In the right image, there are four islands: $[1,1]$, $[4,4]$, $[8,8]$, and $[10,10]$.

inputFormat

The first line contains two integers $n$ and $q$ $(1 \leq n, q \leq 10^5)$, denoting the number of positions and the number of queries respectively.

The second line contains $n$ integers $h_1, h_2, \ldots, h_n$ ($0 \leq h_i \leq 10^9$) representing the altitude of each position.

Then $q$ lines follow, each containing three integers $l_i$, $r_i$, and $x_i$ $(1 \leq l_i \leq r_i \leq n, 0 \leq x_i \leq 10^9)$, where $x_i$ is the rise in sea level for the query.

outputFormat

For each query, output a single integer on a new line representing the number of islands formed in the interval $[l_i, r_i]$ when the sea level rises by $x_i$ meters.

sample

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

2
1