Transmitter Towers

Jakarta has $N$ transmitter towers. The towers lie on a straight line and are numbered from $0$ to $N - 1$ from left to right. For each $i$ with $0 \le i \le N - 1$, the height of tower $i$ is $H[i]$ meters. All tower heights are distinct.

For a positive interference value $\delta$, towers $i$ and $j$ ($0 \le i < j \le N - 1$) can communicate if there is a relay tower $k$ that satisfies both of the following conditions.

• $i < k < j$. That is, tower $i$ is to the left of tower $k$, and tower $j$ is to the right of it.
• The heights of towers $i$ and $j$ are each at most $H[k] - \delta$ meters.

Pak Dengklek wants to rent some towers for her new transmission network. You must answer $Q$ queries. Each query gives parameters $L$, $R$, and $D$ ($0 \le L \le R \le N - 1$, $D > 0$), and asks for the maximum number of towers Pak Dengklek can rent. Assume the following:

• She may rent only towers numbered from $L$ to $R$, inclusive.
• The interference value $\delta$ is $D$.
• Every pair of towers she rents must be able to communicate.

When two rented towers communicate through a relay tower $k$, tower $k$ may or may not be rented.

• $1 \le N \le 100\,000$
• $1 \le Q \le 100\,000$
• $1 \le H[i] \le 10^9$ (for all $0 \le i \le N - 1$)
• $H[i] \ne H[j]$ (for all $0 \le i < j \le N - 1$)
• $0 \le L \le R \le N - 1$
• $1 \le D \le 10^9$