Read problems statements in Mandarin Chinese and Russian.

Sereja has an array consisting of $n$ integers $a_{1}  ≤ a_{2}  ≤ \ldots ≤ 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  ≤  k$) such that $a_{i} + d  ≥  a_{i + 1}$, $a_{i + 1} + d  ≥  a_{i + 2}$, $\ldots$, $a_{k - 1}  +  d ≥  a_{k}$, $a_{k}  ≤  t$ and $a_{k+1} > t$ (if it exists).

Help Sereja find the answer for each query.

------ Input ------
First line of input contains a single integer $n$
Next line contain $n$ space separated integers $a_{1}$, $a_{2}$, $...$, $a_{n}$.
Next line contains a single integer $m$.
Next $m$ lines contain pairs of integers representing the queries.

------ Output ------
For each query, output the answer on a separate line.

------ Constraints ------
$1  ≤  n, m  ≤ 10^{5}$.
$1 ≤  a_{i}  ≤ 10^{6}$
$a_{1}  ≤  t  ≤ 10^{6}$
$0 ≤  d  ≤  10^{6}$

------ Subtasks ------
Subtask 1 (30 points): $1 ≤ n, m ≤ 10^{4}$

Subtask 2 (70 points): No additional constraints.

------ Example Input ------

5
1 2 3 10 50
6
1 1
5 3
11 7
100000 1
1000000 1000000
11 6

------ Example Output ------

1
1
1
5
1
4

见题面

见题面