Wireless Tower Communication

Pak Dengklek has a row of N wireless towers labeled from 0 to N-1, each with a unique height H[i] (in meters). Two towers i and j (with i < j) can communicate under a signal‐interference parameter (\delta > 0) if and only if there exists at least one tower k with (i < k < j) such that

(\displaystyle H[k] \ge \max(H[i], H[j]) + \delta) (in (\LaTeX) format).

Pak Dengklek wants to build his new wireless network by renting some towers. However, his rented towers must have the property that every pair of them can communicate (note that the intermediate tower used for communication may or may not be rented).

For Q queries, each given by three numbers L, R and D (with (0 \le L \le R \le N-1) and (D > 0)), determine the maximum number of towers he can rent among towers in the segment [L, R] (inclusive) such that any two of the rented towers can communicate under (\delta = D).

Note: For any two towers i and j chosen (with i<j), if there is no index k with i<k<j then these two towers cannot communicate.

inputFormat

The first line contains two integers N and Q. The second line contains N space‐separated integers where the i-th integer denotes H[i], the height of tower i. Each of the next Q lines contains three numbers L, R and D representing one query.

outputFormat

For each query, output the maximum number of towers that can be rented in the segment [L, R] so that any two rented towers can communicate, according to the condition described.

sample

5 1
100 150 90 160 120
0 4 10

3