Radio Towers

문제

There are $NN$ radio towers in Jakarta. The towers are located along a straight line and numbered from $00$ to $N-1N\; -\; 1$ from left to right. For each $ii$ such that $0\le i\le N-10\; \backslash le\; i\; \backslash le\; N\; -\; 1$, the height of tower $ii$ is $H[i]H[i]$ metres. The heights of the towers are distinct.

For some positive interference value $\delta \backslash delta$, a pair of towers $ii$ and $jj$ (where $0\le i<j\le N-10\; \backslash le\; i\; \backslash lt\; j\; \backslash le\; N\; -\; 1$) can communicate with each other if and only if there is an intermediary tower $kk$, such that

• tower $ii$ is to the left of tower $kk$ and tower $jj$ is to the right of tower $kk$, that is, $i<k<ji\; \backslash lt\; k\; \backslash lt\; j$, and
• the heights of tower $ii$ and tower $jj$ are both at most $H[k]-\delta H[k]\; -\; \backslash delta$ metres.

Pak Dengklek wants to lease some radio towers for his new radio network. Your task is to answer $QQ$ questions of Pak Dengklek which are of the following form: given parameters $L,RL,\; R$ and $DD$ ($0\le L\le R\le N-10\; \backslash le\; L\; \backslash le\; R\; \backslash le\; N\; -\; 1$ and $D>0D\; >\; 0$), what is the maximum number of towers Pak Dengklek can lease, assuming that

• Pak Dengklek can only lease towers with indices between $LL$ and $RR$ (inclusive), and
• the interference value $\delta \backslash delta$ is $DD$, and
• any pair of radio towers that Pak Dengklek leases must be able to communicate with each other.

Note that two leased towers may communicate using an intermediary tower $kk$, regardless of whether tower $kk$ is leased or not.