Sereja and D

Sereja has an array consisting of $n$ integers $a_{1}  \leq a_{2}  \leq \ldots \leq a_{n}$. Based on this array, he has to answer $m$ queries represented by pairs integers $t$ and $d$. The answer for a query is the smallest integer $i$ for which there exist some $k$ ($i  \leq  k$) such that $a_{i} + d  \geq  a_{i + 1}$, $a_{i + 1} + d  \geq  a_{i + 2}$, $\ldots$, $a_{k - 1}  +  d \geq  a_{k}$,