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

Source: codechef | Difficulty: HARD
Tags: Sorting

Range queries

Segment trees revisited

Complete search

Data structures


Solutions:
import sys
from math import *
from bisect import *
MAX = sys.maxsize
MAXN = 10 ** 5 + 10
logT = [0] * MAXN
for i in range(2, MAXN):
	logT[i] = logT[i // 2] + 1

def buildSparse(a):
	n = len(a)
	k = logT[n] + 1
	st = [[-MAX for j in range(k)] for i in range(n)]
	for i in range(n):
		st[i][0] = a[i]
	j = 1
	while 1 << j <= n:
		i = 0
		while i + (1 << j) - 1 < n:
			st[i][j] = max(st[i][j - 1], st[i + (1 << j - 1)][j - 1])
			i += 1
		j += 1
	return st

def query(l, r, st, d):
	if l > r:
		return False
	tot = r - l + 1
	k = logT[tot]
	return max(st[l][k], st[l + tot - (1 << k)][k]) <= d
n = int(input())
a = [0] + list(map(int, sys.stdin.readline().strip().split()))
m = int(input())
dif = [0] * (n + 1)
for i in range(1, n):
	dif[i] = a[i + 1] - a[i]
st = buildSparse(dif)
for _ in range(m):
	(t, d) = map(int, sys.stdin.readline().strip().split())
	idx = bisect(a, t) - 1
	lo = 1
	hi = idx - 1
	if idx == 1 or a[idx] - a[idx - 1] > d:
		ans = idx
	else:
		while lo < hi:
			mid = (lo + hi) // 2
			if query(mid, idx - 1, st, d):
				hi = mid
			else:
				lo = mid + 1
		ans = lo
	print(ans)