AtCoder Regular Contest 060 - Tak and Hotels

N hotels are located on a straight line. The coordinate of the i-th hotel (1 \leq i \leq N) is x_i.
Tak the traveler has the following two personal principles:
 - He never travels a distance of more than L in a single day.
 - He never sleeps in the open. That is, he must stay at a hotel at the end of a day.
You are given Q queries. The j-th (1 \leq j \leq Q) query is described by two distinct integers a_j and b_j.
For each query, find the minimum number of days that Tak needs to travel from the a_j-th hotel to the b_j-th hotel following his principles.
It is guaranteed that he can always travel from the a_j-th hotel to the b_j-th hotel, in any given input.

-----Constraints-----
 - 2 \leq N \leq 10^5
 - 1 \leq L \leq 10^9
 - 1 \leq Q \leq 10^5
 - 1 \leq x_i < x_2 < ... < x_N \leq 10^9
 - x_{i+1} - x_i \leq L
 - 1 \leq a_j,b_j \leq N
 - a_j \neq b_j
 - N,\,L,\,Q,\,x_i,\,a_j,\,b_j are integers.

-----Partial Score-----
 - 200 points will be awarded for passing the test set satisfying N \leq 10^3 and Q \leq 10^3.

-----Input-----
The input is given from Standard Input in the following format:
N
x_1 x_2 ... x_N
L
Q
a_1 b_1
a_2 b_2
:
a_Q b_Q

-----Output-----
Print Q lines.
The j-th line (1 \leq j \leq Q) should contain the minimum number of days that Tak needs to travel from the a_j-th hotel to the b_j-th hotel.

-----Sample Input-----
9
1 3 6 13 15 18 19 29 31
10
4
1 8
7 3
6 7
8 5

-----Sample Output-----
4
2
1
2

For the 1-st query, he can travel from the 1-st hotel to the 8-th hotel in 4 days, as follows:
 - Day 1: Travel from the 1-st hotel to the 2-nd hotel. The distance traveled is 2.
 - Day 2: Travel from the 2-nd hotel to the 4-th hotel. The distance traveled is 10.
 - Day 3: Travel from the 4-th hotel to the 7-th hotel. The distance traveled is 6.
 - Day 4: Travel from the 7-th hotel to the 8-th hotel. The distance traveled is 10.

Difficulty: HARD

Starter code:

Solutions:
from bisect import bisect
n = int(input())
x = list(map(int, input().split()))
l = int(input())
q = int(input())
r = [[i for i in range(n)] for _ in range(18)]
for j in range(n):
	r[0][j] = bisect(x, x[j] + l) - 1
for i in range(1, 18):
	for j in range(n):
		r[i][j] = r[i - 1][r[i - 1][j]]

def search(x, y):
	res = 0
	cur = x
	i = 17
	while True:
		if i == 0 and r[i][cur] >= y:
			return res + 1
		if r[i][cur] < y:
			cur = r[i][cur]
			res += 1 << i
			continue
		i -= 1
for _ in range(q):
	(a, b) = map(int, input().split())
	print(search(min(a, b) - 1, max(a, b) - 1))


import math
import bisect

def make_tree():
	to = [0] * n
	j = 0
	for i in range(n):
		while x[j + 1] - x[i] <= l:
			j += 1
		to[i] = j
	return to

def binary_lifting():
	m = int(math.log2(n)) + 3
	to2 = [[n - 1] * m for _ in range(n)]
	for i in range(n):
		to2[i][0] = to[i]
	for j in range(1, m):
		for i in range(n):
			to2[i][j] = to2[to2[i][j - 1]][j - 1]
			if to2[i][j] == n - 1:
				break
	return to2

def solve(a, b):
	if a > b:
		(a, b) = (b, a)
	ans = 0
	while True:
		i = bisect.bisect_left(to2[a], b)
		if i == 0:
			if not a == to2[a][0]:
				ans += 1
			break
		a = to2[a][i - 1]
		ans += pow2[i - 1]
	return ans
n = int(input())
x = list(map(int, input().split()))
l = int(input())
inf = 1145141919810
m = int(math.log2(n)) + 3
x.append(inf)
to = make_tree()
to2 = binary_lifting()
q = int(input())
pow2 = [1] * m
for i in range(1, m):
	pow2[i] = 2 * pow2[i - 1]
for _ in range(q):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	ans = solve(a, b)
	print(ans)


import sys

def I():
	return int(sys.stdin.readline().rstrip())

def MI():
	return map(int, sys.stdin.readline().rstrip().split())

def LI():
	return list(map(int, sys.stdin.readline().rstrip().split()))
N = I()
x = LI()
L = I()
from bisect import bisect_right
arrive = [[0] * N for _ in range(30)]
for k in range(30):
	if k == 0:
		for i in range(N):
			arrive[0][i] = bisect_right(x, x[i] + L) - 1
	else:
		for i in range(N):
			arrive[k][i] = arrive[k - 1][arrive[k - 1][i]]

def query(a, b):
	a -= 1
	b -= 1
	ans = 1
	for k in range(29, -1, -1):
		if arrive[k][a] >= b:
			continue
		else:
			a = arrive[k][a]
			ans += 1 << k
	print(ans)
Q = I()
for i in range(Q):
	(a, b) = MI()
	if a > b:
		(a, b) = (b, a)
	query(a, b)


def solve():
	n = int(input())
	arr = list(map(int, input().split()))
	L = int(input())
	dp = [[0] * 20 for _ in range(n)]
	for i in range(n):
		(l, r) = (i, n)
		while l < r:
			mid = l + r >> 1
			if arr[mid] - arr[i] <= L:
				l = mid + 1
			else:
				r = mid
		dp[i][0] = r - 1
	for j in range(1, 20):
		for i in range(n):
			dp[i][j] = dp[dp[i][j - 1]][j - 1]
	q = int(input())
	for _ in range(q):
		(x, y) = list(map(int, input().split()))
		x -= 1
		y -= 1
		if x > y:
			(x, y) = (y, x)
		tmp = 0
		for j in range(19, -1, -1):
			if dp[x][j] < y:
				tmp += 1 << j
				x = dp[x][j]
		print(tmp + 1)
solve()


from bisect import bisect_left, bisect_right
N = int(input())
x = list(map(int, input().split()))
L = int(input())
n = N.bit_length() + 1
next_hotel = [[0] * n for _ in range(N)]
for i in range(N):
	index = bisect_right(x, x[i] + L) - 1
	if index == i:
		next_hotel[i][0] = N
	else:
		next_hotel[i][0] = index
for i in range(1, n):
	for j in range(N):
		if next_hotel[j][i - 1] < N:
			index = next_hotel[next_hotel[j][i - 1]][i - 1]
			if index == j:
				next_hotel[j][i] = N
			else:
				next_hotel[j][i] = index
		else:
			next_hotel[j][i] = N

def count(a, b):
	if a > b:
		(a, b) = (b, a)
	res = 0
	for i in range(n):
		if a >= b:
			return res
		c = max(0, bisect_left(next_hotel[a], b) - 1)
		a = next_hotel[a][c]
		res += 2 ** c
Q = int(input())
for _ in range(Q):
	(a, b) = map(int, input().split())
	print(count(a - 1, b - 1))


from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random

def LI():
	return list(map(int, sys.stdin.readline().split()))

def I():
	return int(sys.stdin.readline())

def LS():
	return list(map(list, sys.stdin.readline().split()))

def S():
	return list(sys.stdin.readline())[:-1]

def IR(n):
	l = [None for i in range(n)]
	for i in range(n):
		l[i] = I()
	return l

def LIR(n):
	l = [None for i in range(n)]
	for i in range(n):
		l[i] = LI()
	return l

def SR(n):
	l = [None for i in range(n)]
	for i in range(n):
		l[i] = S()
	return l

def LSR(n):
	l = [None for i in range(n)]
	for i in range(n):
		l[i] = SR()
	return l
mod = 1000000007

def A():
	return

def B():
	return

def C():
	n = I()
	x = LI()
	l = I()
	k = int(math.log(n, 2))
	f = [[i for j in range(k + 1)] for i in range(n)]
	for i in range(n - 1):
		j = bisect.bisect_left(x, x[i] + l)
		if j < n:
			if x[j] > x[i] + l:
				f[i][0] = j - 1
			else:
				f[i][0] = j
		else:
			f[i][0] = j - 1
	po2 = [1] * (k + 1)
	for i in range(k):
		po2[i + 1] = po2[i] * 2
	for j in range(k):
		for i in range(n):
			f[i][j + 1] = f[f[i][j]][j]
	q = I()
	for i in range(q):
		(a, b) = LI()
		(a, b) = [min(a, b) - 1, max(a, b) - 1]
		ans = 0
		while a < b:
			i = bisect.bisect_left(f[a], b)
			ans += po2[max(0, i - 1)]
			a = f[a][max(0, i - 1)]
		print(ans)

def D():
	return

def E():
	return

def F():
	return

def G():
	return

def H():
	return

def __starting_point():
	C()
__starting_point()


import bisect
n = int(input())
x = list(map(int, input().split()))
l = int(input())
q = int(input())
info = [list(map(int, input().split())) for i in range(q)]
log_table = [[0] * n for i in range(17)]
for i in range(n):
	log_table[0][i] = bisect.bisect_right(x, x[i] + l) - 1
for j in range(1, 17):
	for i in range(n):
		log_table[j][i] = log_table[j - 1][log_table[j - 1][i]]

def solve(_from, to, day):
	pos = _from
	i = 0
	while day:
		if day // 2 > 0:
			if day % 2 == 1:
				pos = log_table[i][pos]
			i += 1
			day = day // 2
		else:
			if day % 2 == 1:
				pos = log_table[i][pos]
			break
	if to <= pos:
		return True
	else:
		return False
for i in range(q):
	ok = n - 1
	ng = 0
	(start, goal) = info[i]
	start -= 1
	goal -= 1
	if start > goal:
		(start, goal) = (goal, start)
	while abs(ok - ng) > 1:
		mid = (ok + ng) // 2
		if solve(start, goal, mid):
			ok = mid
		else:
			ng = mid
	print(ok)


import sys
input = sys.stdin.readline
from bisect import bisect
n = int(input())
x = list(map(int, input().split()))
l = int(input())
m = 20
par = [[-1] * n for i in range(m)]
for i in range(n):
	j = bisect(x, x[i] + l) - 1
	par[0][i] = j
for i in range(m - 1):
	for j in range(n):
		par[i + 1][j] = par[i][par[i][j]]

def hoge(x, y):
	k = 0
	for i in range(m)[::-1]:
		if par[i][x] < y:
			k += 1 << i
			x = par[i][x]
	return k + 1
q = int(input())
ans = []
for i in range(q):
	(a, b) = map(int, input().split())
	(a, b) = (a - 1, b - 1)
	if a > b:
		(a, b) = (b, a)
	print(hoge(a, b))


import sys
read = sys.stdin.read
readline = sys.stdin.readline
(n,) = map(int, readline().split())
(*x,) = map(int, readline().split())
(l, q, *ab) = map(int, read().split())
from bisect import bisect_left, bisect_right
M = 19
R = [[bisect_right(x, i + l) - 1 for i in x]]
for i in range(M):
	RR = [R[-1][R[-1][i]] for i in range(n)]
	R.append(RR)
mp = iter(ab)
for (a, b) in zip(mp, mp):
	a -= 1
	b -= 1
	if a > b:
		(a, b) = (b, a)
	ans = 0
	for i in range(M, -1, -1):
		if R[i][a] < b:
			ans += 1 << i
			a = R[i][a]
	print(ans + 1)


import sys
input = sys.stdin.readline
from bisect import bisect_right
n = int(input())
X = tuple(map(int, input().split()))
l = int(input())
q = int(input())
D = [[0] * n for _ in range(18)]
for i in range(n):
	D[0][i] = bisect_right(X, X[i] + l) - 1
for k in range(1, 18):
	for i in range(n):
		D[k][i] = D[k - 1][D[k - 1][i]]

def query(a, b):
	ret = 0
	while True:
		for k in range(18):
			if D[k][a] >= b:
				break
		if k == 0:
			ret += 1
			return ret
		k -= 1
		ret += pow(2, k)
		a = D[k][a]
for _ in range(q):
	(a, b) = map(int, input().split())
	if a > b:
		(a, b) = (b, a)
	a -= 1
	b -= 1
	print(query(a, b))


from collections import deque
from bisect import bisect_right, bisect_left
N = int(input())
x = list(map(int, input().split()))
L = int(input())
K = 0
tmp = 1
while tmp <= N:
	tmp *= 2
	K += 1
parent = [[None] * N for _ in range(K)]
parent[0][N - 1] = N - 1
for i in range(N - 1):
	d = bisect_right(x, x[i] + L)
	parent[0][i] = d - 1
for k in range(1, K):
	for i in range(N):
		parent[k][i] = parent[k - 1][parent[k - 1][i]]
Q = int(input())
for _ in range(Q):
	ans = 0
	(a, b) = [int(x) - 1 for x in input().split()]
	if a > b:
		(a, b) = (b, a)
	for i in range(K - 1, -1, -1):
		if parent[i][a] < b:
			a = parent[i][a]
			ans += pow(2, i)
	print(ans + 1)


N = int(input())
X = list(map(int, input().split()))
L = int(input())

def one_step(i):
	goal = X[i] + L
	low = 0
	high = N
	while high - low > 1:
		mid = (high + low) // 2
		if X[mid] <= goal:
			low = mid
		else:
			high = mid
	return low
onesteps = [one_step(i) for i in range(N)]

def double(layer):
	return [layer[layer[i]] for i in range(N)]
NUM_LAYERS = 20
layers = [onesteps]
for _ in range(NUM_LAYERS):
	layers.append(double(layers[-1]))

def query(a, b):
	if a > b:
		(a, b) = (b, a)
	ans = 0
	while a < b:
		ind = 0
		while layers[ind + 1][a] < b:
			ind += 1
		ans += 2 ** ind
		a = layers[ind][a]
	return ans
Q = int(input())
for _ in range(Q):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	print(query(a, b))


n = int(input())
hot = list(map(int, input().split()))
n_ = n.bit_length()
db = [[n - 1] * n]
L = int(input())
r = 1
for i in range(n - 1):
	while r < n - 1 and hot[r + 1] - hot[i] <= L:
		r += 1
	db[0][i] = r
for j in range(1, n_ + 1):
	new = [db[-1][db[-1][i]] for i in range(n)]
	db.append(new)
	if new[0] == n - 1:
		break
n_ = len(db)

def query(s, t):
	dt = 0
	for j in range(n_ - 1, 0, -1):
		if db[j][s] < t:
			dt += 2 ** j
			s = db[j][s]
	while s < t:
		dt += 1
		s = db[0][s]
	return dt
q = int(input())
for _ in range(q):
	(s, t) = map(int, input().split())
	if t < s:
		(s, t) = (t, s)
	print(query(s - 1, t - 1))


from bisect import bisect_left, bisect_right
import math
import sys
input = sys.stdin.readline

def main():
	N = int(input())
	X = list(map(int, input().split()))
	L = int(input())
	ln = int(math.log(N, 2))
	dpl = [[0] * N for _ in range(ln + 1)]
	dpr = [[0] * N for _ in range(ln + 1)]
	l = 0
	r = 0
	for i in range(N):
		x = X[i]
		while X[l] + L < x:
			l += 1
		while r < N - 1 and x + L >= X[r + 1]:
			r += 1
		dpl[0][i] = l
		dpr[0][i] = r
	for k in range(1, ln + 1):
		for i in range(N):
			dpl[k][i] = dpl[k - 1][dpl[k - 1][i]]
			dpr[k][i] = dpr[k - 1][dpr[k - 1][i]]
	Q = int(input())
	for _ in range(Q):
		(a, b) = list(map(int, input().split()))
		a -= 1
		b -= 1
		ans = 0
		if a < b:
			for k in range(ln + 1)[::-1]:
				if dpr[k][a] < b:
					a = dpr[k][a]
					ans += 2 ** k
		else:
			for k in range(ln + 1)[::-1]:
				if dpl[k][a] > b:
					a = dpl[k][a]
					ans += 2 ** k
		print(ans + 1)

def __starting_point():
	main()
__starting_point()


def examE():
	N = I()
	X = LI()
	L = I()
	Q = I()
	n = N.bit_length() + 1
	dp = [[0] * n for _ in range(N)]
	for i in range(N):
		dp[i][0] = bisect.bisect_right(X, X[i] + L) - 1
	for i in range(1, n):
		for j in range(N):
			if dp[j][i - 1] < N:
				index = dp[dp[j][i - 1]][i - 1]
				if index == j:
					dp[j][i] = N
				else:
					dp[j][i] = index
			else:
				dp[j][i] = N

	def fast_day(a, b):
		if a > b:
			(a, b) = (b, a)
		res = 0
		for i in range(n):
			if a >= b:
				return res
			c = max(0, bisect.bisect_left(dp[a], b) - 1)
			a = dp[a][c]
			res += 2 ** c
	for _ in range(Q):
		(a, b) = list(map(int, input().split()))
		print(fast_day(a - 1, b - 1))
import sys, copy, bisect, itertools, heapq, math
from heapq import heappop, heappush, heapify
from collections import Counter, defaultdict, deque

def I():
	return int(sys.stdin.readline())

def LI():
	return list(map(int, sys.stdin.readline().split()))

def LS():
	return sys.stdin.readline().split()

def S():
	return sys.stdin.readline().strip()
mod = 10 ** 9 + 7
inf = float('inf')
examE()


from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, groupby
import sys
import bisect
import string
import math
import time
import random

def S_():
	return input()

def LS():
	return [i for i in input().split()]

def I():
	return int(input())

def MI():
	return map(int, input().split())

def LI():
	return [int(i) for i in input().split()]

def LI_():
	return [int(i) - 1 for i in input().split()]

def NI(n):
	return [int(input()) for i in range(n)]

def NI_(n):
	return [int(input()) - 1 for i in range(n)]

def StoI():
	return [ord(i) - 97 for i in input()]

def ItoS(nn):
	return chr(nn + 97)

def LtoS(ls):
	return ''.join([chr(i + 97) for i in ls])

def GI(V, E, Directed=False, index=0):
	org_inp = []
	g = [[] for i in range(n)]
	for i in range(E):
		inp = LI()
		org_inp.append(inp)
		if index == 0:
			inp[0] -= 1
			inp[1] -= 1
		if len(inp) == 2:
			(a, b) = inp
			g[a].append(b)
			if not Directed:
				g[b].append(a)
		elif len(inp) == 3:
			(a, b, c) = inp
			aa = (inp[0], inp[2])
			bb = (inp[1], inp[2])
			g[a].append(bb)
			if not Directed:
				g[b].append(aa)
	return (g, org_inp)

def bit_combination(k, n=2):
	rt = []
	for tb in range(n ** k):
		s = [tb // n ** bt % n for bt in range(k)]
		rt += [s]
	return rt

def show(*inp, end='\n'):
	if show_flg:
		print(*inp, end=end)
YN = ['Yes', 'No']
mo = 10 ** 9 + 7
inf = float('inf')
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
input = lambda : sys.stdin.readline().rstrip()

def ran_input():
	import random
	n = random.randint(4, 16)
	(rmin, rmax) = (1, 10)
	a = [random.randint(rmin, rmax) for _ in range(n)]
	return (n, a)
show_flg = False
show_flg = True
ans = 0
n = I()
m = n.bit_length()
x = LI()
L = I()
q = I()
r = [0] * n
for i in range(n):
	r[i] = bisect.bisect(x, x[i] + L) - 1
nb = [r]
nx = [0] * n
for k in range(m):
	nx = [0] * n
	for i in range(n):
		nx[i] = r[r[i]]
	nb.append(nx)
	r = nx
for _ in range(q):
	(a, b) = LI_()
	if a > b:
		(a, b) = (b, a)
	t = 0
	for p in range(m, -1, -1):
		if nb[p][a] < b:
			t += 1 << p
			a = nb[p][a]
	print(t + 1)


from bisect import bisect
N = int(input())
X = [int(x) for x in input().split()]
L = int(input())
inf = float('inf')
X.append(X[-1] + L)
Table = [[inf] * 18 for i in range(N)]
r = 1
for i in range(N):
	if r <= N:
		while X[r] - X[i] <= L:
			r += 1
			if r > N:
				break
	Table[i][0] = r - 1
for k in range(1, 18):
	for i in range(N):
		if Table[i][k - 1] == N:
			Table[i][k] = N
			continue
		Table[i][k] = Table[Table[i][k - 1]][k - 1]
Q = int(input())
for q in range(Q):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	ans = 0
	if a > b:
		(a, b) = (b, a)
	while a < b:
		i = bisect(Table[a], b) - 1
		if i >= 0:
			ans += 2 ** i
		else:
			ans += 1
		a = Table[a][i]
	print(ans)


N = int(input())
(*X,) = map(int, input().split())
L = int(input())
K = 20
D = [[N] * (K + 1) for i in range(N)]
j = N - 1
for i in range(N - 1, -1, -1):
	while j > 0 and X[j] - X[i] > L:
		j -= 1
	D[i][0] = j
for k in range(K):
	for i in range(N):
		if D[i][k] != N:
			D[i][k + 1] = D[D[i][k]][k]

def solve(a, b):
	if not a < b:
		(a, b) = (b, a)
	res = 1
	for k in range(K, -1, -1):
		if D[a][k] < b:
			a = D[a][k]
			res += 2 ** k
	return res
Q = int(input())
ans = []
for i in range(Q):
	(a, b) = map(int, input().split())
	ans.append(solve(a - 1, b - 1))
print(*ans, sep='\n')


import bisect
import sys
input = sys.stdin.readline

def calc():
	n = int(input())
	arr = list(map(int, input().split()))
	l = int(input())
	pos = 0
	dbl = [[0] * (n + 1)]
	for i in range(n):
		dbl[0][i + 1] = bisect.bisect_right(arr, arr[i] + l)
	for _ in range(n.bit_length() - 1):
		tmp = [0] * (n + 1)
		for i in range(n + 1):
			tmp[i] = dbl[-1][dbl[-1][i]]
		dbl.append(tmp)
	q = int(input())
	for _ in range(q):
		(a, b) = map(int, input().split())
		if a > b:
			(a, b) = (b, a)
		l = 0
		r = b - a + 1
		while r - l != 1:
			mid = (l + r) // 2
			tmp = a
			for i in range(mid.bit_length()):
				if mid & 1 << i:
					tmp = dbl[i][tmp]
			if tmp >= b:
				r = mid
			else:
				l = mid
		print(r)
calc()


import sys
input = sys.stdin.readline
import numpy as np
N = int(input())
X = np.array(input().split(), dtype=np.int64)
L = int(input())
U = N.bit_length()
next_x = []
next_x.append(np.searchsorted(X, X + L, side='right') - 1)
for i in range(U):
	next_x.append(next_x[i][next_x[i]])

def days(a, b):
	a -= 1
	b -= 1
	if b < a:
		(a, b) = (b, a)
	result = 0
	for n in range(U, -1, -1):
		c = next_x[n][a]
		if c < b:
			a = c
			result += 1 << n
	return result + 1
Q = int(input())
for _ in range(Q):
	(a, b) = map(int, input().split())
	print(days(a, b))


import sys
input = sys.stdin.readline
import bisect
n = int(input())
X = list(map(int, input().split()))
l = int(input())
U = 17
dp = [[0] * n for _ in range(U + 1)]
for (i, x) in enumerate(X):
	t = bisect.bisect_left(X, x + l)
	dp[0][i] = bisect.bisect_right(X, x + l) - 1
for k in range(U):
	for i in range(n):
		dp[k + 1][i] = dp[k][dp[k][i]]

def test(x, a, b):
	for i in range(U, -1, -1):
		if x >> i & 1:
			a = dp[i][a]
	return a >= b

def solve(a, b):
	if a > b:
		(a, b) = (b, a)
	ng = 0
	ok = n - 1
	while ok - ng > 1:
		mid = (ng + ok) // 2
		if test(mid, a, b):
			ok = mid
		else:
			ng = mid
	print(ok)
q = int(input())
for _ in range(q):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	solve(a, b)


import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10 ** 9))
write = lambda x: sys.stdout.write(x + '\n')
n = int(input())
x = list(map(int, input().split()))
l = int(input())
q = int(input())
ps = [None] * n
j = 0
for i in range(n):
	if j < i:
		j = i
	while j + 1 < n and x[j + 1] - x[i] <= l:
		j += 1
	ps[i] = j

def double(ps):
	k = 0
	n = len(ps)
	while pow(2, k) < n:
		k += 1
	prev = [[None] * n for _ in range(k)]
	for j in range(n):
		prev[0][j] = ps[j]
	for i in range(1, k):
		for j in range(n):
			p = prev[i - 1][j]
			if p >= 0:
				prev[i][j] = prev[i - 1][p]
			else:
				prev[i][j] = p
	return prev
dl = double(ps)
ans = [None] * q

def sub(a, b, x):
	for k in range(len(dl) - 1, -1, -1):
		if x >= pow(2, k):
			x -= pow(2, k)
			a = dl[k][a]
	return a >= b
for i in range(q):
	(a, b) = map(lambda x: int(x) - 1, input().split())
	(a, b) = (min(a, b), max(a, b))
	res = 0
	tmp = float('inf')
	l = 0
	r = n
	while l + 1 < r:
		m = (l + r) // 2
		if sub(a, b, m):
			r = m
		else:
			l = m
	ans[i] = r
write('\n'.join(map(str, ans)))


from bisect import bisect
N = int(input())
xs = list(map(int, input().split()))
L = int(input())
Q = int(input())
qs = [tuple(map(lambda x: int(x) - 1, input().split())) for i in range(Q)]
K = len(bin(N)) - 1
dp = [[None] * N for i in range(K)]
for (i, x) in enumerate(xs):
	dp[0][i] = bisect(xs, x + L) - 1
for k in range(K - 1):
	for i in range(N):
		dp[k + 1][i] = dp[k][dp[k][i]]

def enough(fr, to, n):
	now = fr
	bn = bin(n)
	ln = len(bn) - 2
	for (i, c) in enumerate(bn[2:]):
		if c == '0':
			continue
		now = dp[ln - 1 - i][now]
		if now >= to:
			return True
	return False
ans = []
for (a, b) in qs:
	if a > b:
		(a, b) = (b, a)
	ok = N
	ng = 0
	while ok - ng > 1:
		m = (ok + ng) // 2
		if enough(a, b, m):
			ok = m
		else:
			ng = m
	ans.append(ok)
print(*ans, sep='\n')


import sys, queue, math, copy, itertools, bisect, collections, heapq

def main():
	sys.setrecursionlimit(10 ** 7)
	INF = 10 ** 18
	MOD = 10 ** 9 + 7
	LI = lambda : [int(x) for x in sys.stdin.readline().split()]
	_LI = lambda : [int(x) - 1 for x in sys.stdin.readline().split()]
	NI = lambda : int(sys.stdin.readline())
	SI = lambda : sys.stdin.readline().rstrip()
	N = NI()
	x = LI() + [INF]
	L = NI()
	m = N.bit_length()
	f = [[N - 1] * N for _ in range(m)]
	j = 1
	for i in range(N - 1):
		while x[i] + L >= x[j + 1]:
			j += 1
			if j >= N - 1:
				break
		f[0][i] = j
	for k in range(1, m):
		for i in range(N):
			f[k][i] = f[k - 1][f[k - 1][i]]
	for _ in range(NI()):
		ans = 0
		(a, b) = _LI()
		if a > b:
			(a, b) = (b, a)
		for k in range(m - 1, -1, -1):
			if f[k][a] < b:
				a = f[k][a]
				ans += 2 ** k
		print(ans + 1)
main()


import sys
input = sys.stdin.readline
import bisect

def main():
	n = int(input())
	X = list(map(int, input().split()))
	l = int(input())
	U = 17
	dp = [[0] * n for _ in range(U + 1)]
	for (i, x) in enumerate(X):
		t = bisect.bisect_left(X, x + l)
		dp[0][i] = bisect.bisect_right(X, x + l) - 1
	for k in range(U):
		for i in range(n):
			dp[k + 1][i] = dp[k][dp[k][i]]
	q = int(input())
	for _ in range(q):
		(a, b) = map(int, input().split())
		a -= 1
		b -= 1
		if a > b:
			(a, b) = (b, a)
		res = 1
		for k in range(U, -1, -1):
			if dp[k][a] < b:
				a = dp[k][a]
				res += 1 << k
		print(res)
main()


import bisect

def dist(tree, tree_i, tree_j, parent, a, b):
	i = tree_i[b]
	if tree_i[a] == i:
		return tree_j[b] - tree_j[a]
	else:
		branch = tree[i]
		branch_root = branch[0]
		if branch_root < a:
			return tree_j[b] - bisect.bisect_left(branch, a) + 1
		else:
			p = parent[branch_root]
			if p < a:
				return tree_j[b] + 1
			else:
				return tree_j[b] + 1 + dist(tree, tree_i, tree_j, parent, a, p)

def solve(n, x, l, q, qry):
	g = [[] for _ in range(n)]
	parent = [-1] * n
	weight = [1] * n
	for v in range(1, n):
		p = bisect.bisect_left(x, x[v] - l)
		g[p].append(v)
		parent[v] = p
	for v in range(n - 1, -1, -1):
		for w in g[v]:
			weight[v] += weight[w]
	tree = [[0]]
	tree_i = [-1] * n
	tree_j = [0] * n
	tree_i[0] = 0
	for v in range(n):
		mw = 0
		c = -1
		for w in g[v]:
			if mw < weight[w]:
				mw = weight[w]
				c = w
		if 0 <= c:
			i = tree_i[v]
			tree[i].append(c)
			tree_i[c] = i
			tree_j[c] = len(tree[i]) - 1
			for w in g[v]:
				if w != c:
					tree.append([w])
					tree_i[w] = len(tree) - 1
	for tpl in qry:
		(a, b) = tpl
		if b < a:
			(a, b) = (b, a)
		print(dist(tree, tree_i, tree_j, parent, a, b))

def main():
	n = input()
	n = int(n)
	x = list(map(int, input().split()))
	l = input()
	l = int(l)
	q = input()
	q = int(q)
	qry = []
	for _ in range(q):
		(a, b) = input().split()
		a = int(a) - 1
		b = int(b) - 1
		qry.append((a, b))
	solve(n, x, l, q, qry)

def __starting_point():
	main()
__starting_point()


import sys, bisect
input = sys.stdin.readline
N = int(input())
x = list(map(int, input().split()))
L = int(input())
doubling = [[-1 for i in range(N)] for j in range(20)]
backdoubling = [[-1 for i in range(N)] for j in range(20)]
for i in range(N):
	npos = x[i] + L
	index = bisect.bisect_right(x, npos)
	doubling[0][i] = index - 1
for i in range(1, 20):
	for j in range(N):
		doubling[i][j] = doubling[i - 1][doubling[i - 1][j]]
for i in range(N):
	npos = x[i] - L
	index = bisect.bisect_left(x, npos)
	backdoubling[0][i] = index
for i in range(1, 20):
	for j in range(N):
		backdoubling[i][j] = backdoubling[i - 1][backdoubling[i - 1][j]]

def forward(num, start):
	for i in range(20):
		if num >> i & 1 == 1:
			start = doubling[i][start]
	return start

def back(num, start):
	for i in range(20):
		if num >> i & 1 == 1:
			start = backdoubling[i][start]
	return start
for _ in range(int(input())):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	if b >= a:
		s = 0
		e = N
		while e - s > 1:
			test = (e + s) // 2
			if forward(test, a) >= b:
				e = test
			else:
				s = test
		if forward(s, a) >= b:
			print(s)
		else:
			print(e)
	else:
		s = 0
		e = N
		while e - s > 1:
			test = (e + s) // 2
			if b >= back(test, a):
				e = test
			else:
				s = test
		if b >= back(s, a):
			print(s)
		else:
			print(e)


import bisect
n = int(input())
x = [int(item) for item in input().split()]
l = int(input())
q = int(input())
ab = []
for i in range(q):
	(a, b) = [int(item) for item in input().split()]
	a -= 1
	b -= 1
	if a > b:
		(a, b) = (b, a)
	ab.append((a, b))
dt = [[0] * n for _ in range(18)]
for (i, item) in enumerate(x):
	dt[0][i] = bisect.bisect_right(x, item + l) - 1
for i in range(1, 18):
	for j in range(n):
		dt[i][j] = dt[i - 1][dt[i - 1][j]]
for (a, b) in ab:
	days = 0
	if a == b:
		print(days)
		continue
	for i in range(17, -1, -1):
		if dt[i][a] < b:
			a = dt[i][a]
			days += 2 ** i
	print(days + 1)


import bisect

def wantp(p, day):
	for i in range(len(db)):
		i = len(db) - 1 - i
		if day & 2 ** i > 0:
			p = db[i][p]
	return p
N = int(input())
x = list(map(int, input().split()))
L = int(input())
able = []
for i in range(N):
	able.append(bisect.bisect_right(x, x[i] + L) - 1)
db = [able]
while min(db[-1]) != N - 1:
	new = []
	for i in range(N):
		new.append(db[-1][db[-1][i]])
	db.append(new)
Q = int(input())
for loop in range(Q):
	(a, b) = list(map(int, input().split()))
	if a > b:
		t = a
		a = b
		b = t
	a -= 1
	b -= 1
	l = 0
	r = 2 ** len(db)
	while r - l != 1:
		m = (l + r) // 2
		np = wantp(a, m)
		if np < b:
			l = m
		else:
			r = m
	print(r)


import bisect
n = int(input())
arr = list(map(int, input().split()))
l = int(input())
pos = 0
dbl = [[0] * (n + 1)]
for i in range(n):
	dbl[0][i + 1] = bisect.bisect_right(arr, arr[i] + l)
for _ in range(20):
	tmp = [0] * (n + 1)
	for i in range(n + 1):
		tmp[i] = dbl[-1][dbl[-1][i]]
	dbl.append(tmp)
q = int(input())
for _ in range(q):
	(a, b) = map(int, input().split())
	if a > b:
		(a, b) = (b, a)
	l = 0
	r = b - a + 1
	while r - l != 1:
		mid = (l + r) // 2
		tmp = a
		for i in range(20):
			if mid & 1 << i:
				tmp = dbl[i][tmp]
		if tmp >= b:
			r = mid
		else:
			l = mid
	print(r)


n = int(input())
x = list(map(int, input().split()))
l = int(input())
q = int(input())
ab = [list(map(int, input().split())) for i in range(q)]
keta = len(format(n + 1, 'b'))
nxt = [[0 for _ in range(n)] for _ in range(keta)]
import bisect
for i in range(n):
	num = x[i] + l
	ind = bisect.bisect_right(x, num)
	nxt[0][i] = ind - 1
for k in range(1, keta):
	for i in range(n):
		nxt[k][i] = nxt[k - 1][nxt[k - 1][i]]

def solve(s, g, day):
	bi = format(day, 'b')
	keta = len(bi) - 1
	for b in bi:
		if b == '1':
			s = nxt[keta][s]
		keta -= 1
	return s >= g
for (a, b) in ab:
	s = min(a, b)
	g = max(a, b)
	l = 0
	r = n
	while r - l > 1:
		mid = (l + r) // 2
		if solve(s - 1, g - 1, mid):
			r = mid
		else:
			l = mid
	print(r)


import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
import bisect
n = int(readline())
x = list(map(int, readline().split()))
l = int(readline())
q = int(readline())
ab = list(map(int, read().split()))
dbl = [[] for _ in range(n)]
j = 0
for i in range(n):
	while j < n - 1:
		if abs(x[j + 1] - x[i]) > l:
			break
		j += 1
	dbl[i].append(j)
for i in range(30):
	if dbl[0][-1] == n - 1:
		break
	for j in range(n):
		dbl[j].append(dbl[dbl[j][i]][i])

def calc(a, b):
	if dbl[a][0] >= b:
		return 1
	ind = bisect.bisect_left(dbl[a], b) - 1
	return 2 ** ind + calc(dbl[a][ind], b)
ans = []
it = iter(ab)
for (a, b) in zip(it, it):
	a -= 1
	b -= 1
	(a, b) = (min(a, b), max(a, b))
	ans.append(calc(a, b))
print('\n'.join(map(str, ans)))


import bisect
N = int(input())
x = list(map(int, input().split()))
L = int(input())
dest = []
dest_1 = [0] * N
for i in range(N):
	dest_1[i] = bisect.bisect_left(x, x[i] + L + 0.5) - 1
dest.append(dest_1)
for i in range(1, len(bin(N - 1)) - 1):
	dest_prev = dest[i - 1]
	dest_i = [0] * N
	for j in range(N):
		dest_i[j] = dest_prev[dest_prev[j]]
	dest.append(dest_i)
Q = int(input())
for _ in range(Q):
	(a, b) = list(map(int, input().split()))
	a -= 1
	b -= 1
	if a > b:
		(a, b) = (b, a)
	k = len(dest) - 1
	ans = 0
	while True:
		d = dest[k][a]
		if d >= b:
			if k > 0:
				k -= 1
			else:
				ans += 1
				break
		else:
			ans += 2 ** k
			a = d
	print(ans)


import sys
from bisect import bisect
n = int(input())
xxx = list(map(int, input().split()))
l = int(input())
reachable = [[bisect(xxx, x + l) - 1 for x in xxx]]
while reachable[-1][0] < n - 1:
	rp = reachable[-1]
	reachable.append(list(map(rp.__getitem__, rp)))
q = int(input())
buf = []
for line in sys.stdin:
	(a, b) = map(int, line.split())
	a -= 1
	b -= 1
	if a > b:
		(a, b) = (b, a)
	ans = 0
	for i in range(len(reachable) - 1, -1, -1):
		ria = reachable[i][a]
		if ria >= b:
			continue
		ans += 1 << i
		a = ria
	if a != b:
		ans += 1
	buf.append(ans)
print('\n'.join(map(str, buf)))


import sys
input = sys.stdin.readline
N = int(input())
a = list(map(int, input().split()))
L = int(input())
k = 1
while a[-1] // (L * pow(2, k)):
	k += 1
e = [[0] * k for _ in range(N)]
for i in range(N):
	t = L + a[i]
	ok = i
	ng = N
	while ng - ok > 1:
		m = (ok + ng) // 2
		if a[m] <= t:
			ok = m
		else:
			ng = m
	e[i][0] = ok
for j in range(len(e[i]) - 1):
	for i in range(N):
		x = e[i][j]
		e[i][j + 1] = e[x][j]

def doubling(u, v):
	if u == v:
		return 0
	ok = -1
	ng = len(e[u])
	while ng - ok > 1:
		m = (ok + ng) // 2
		if e[u][m] < v:
			ok = m
		else:
			ng = m
	if ok < 0:
		return 1
	return doubling(e[u][ok], v) + pow(2, ok)
Q = int(input())
for _ in range(Q):
	(x, y) = map(int, input().split())
	x -= 1
	y -= 1
	if x > y:
		(x, y) = (y, x)
	print(doubling(x, y))


from bisect import bisect_right
from math import log
N = int(input())
X = list(map(int, input().split()))
L = int(input())
R = [[-1] * N for i in range(int(log(N, 2) + 1))]
for i in range(N):
	R[0][i] = bisect_right(X, X[i] + L) - 1
for k in range(1, len(R)):
	for i in range(N):
		R[k][i] = R[k - 1][R[k - 1][i]]
Q = int(input())
for q in range(Q):
	(a, b) = map(int, input().split())
	(a, b) = (min(a, b) - 1, max(a, b) - 1)
	ans = 0
	for k in range(len(R))[::-1]:
		if R[k][a] < b:
			a = R[k][a]
			ans += 2 ** k
	print(ans + 1)


import bisect
n = int(input())
x = [int(s) - 1 for s in input().split()]
l = int(input())
q = int(input())
p = [[0] * 17 for _ in range(n)]
for i in range(n):
	p[i][0] = bisect.bisect_right(x, x[i] + l) - 1
for i in range(1, 17):
	for j in range(n):
		p[j][i] = p[p[j][i - 1]][i - 1]
for _ in range(q):
	(a, b) = sorted((int(s) - 1 for s in input().split()))
	r = 0
	for i in reversed(range(17)):
		if p[a][i] < b:
			a = p[a][i]
			r += 1 << i
	print(r + 1)


from bisect import *
n = int(input())
x = list(map(int, input().split()))
l = int(input())
q = int(input())
dp_plus = [[0] * (n + 1) for i in range(30)]
dp_minus = [[0] * (n + 1) for i in range(30)]
for i in range(n):
	now = x[i]
	reach = now + l
	dp_plus[0][i + 1] = bisect_right(x, reach)
for i in range(n):
	now = x[i]
	reach = now - l
	dp_minus[0][i + 1] = bisect_left(x, reach) + 1
for i in range(29):
	for j in range(1, n + 1):
		dp_plus[i + 1][j] = dp_plus[i][dp_plus[i][j]]
		dp_minus[i + 1][j] = dp_minus[i][dp_minus[i][j]]
for _ in range(q):
	(a, b) = list(map(int, input().split()))
	ans = 1
	if a < b:
		for i in range(29, -1, -1):
			if dp_plus[i][a] < b:
				a = dp_plus[i][a]
				ans += pow(2, i)
	else:
		for i in range(29, -1, -1):
			if dp_minus[i][a] > b:
				a = dp_minus[i][a]
				ans += pow(2, i)
	print(ans)


from bisect import bisect_right
N = int(input())
X = list(map(int, input().split()))
L = int(input())
P = [[0] * N for i in range(30)]
for i in range(N):
	q = bisect_right(X, X[i] + L)
	P[0][i] = q - 1
for i in range(1, 30):
	for j in range(N):
		P[i][j] = P[i - 1][P[i - 1][j]]
Q = int(input())
for i in range(Q):
	(a, b) = map(int, input().split())
	if a > b:
		(a, b) = (b, a)
	(a, b) = (a - 1, b - 1)
	num = 0
	for j in range(29, -1, -1):
		if P[j][a] < b:
			a = P[j][a]
			num += 2 ** j
	print(num + 1)


from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, cos, radians, pi, sin
from operator import mul
from functools import reduce
from operator import mul
sys.setrecursionlimit(2147483647)
INF = 10 ** 13

def LI():
	return list(map(int, sys.stdin.buffer.readline().split()))

def I():
	return int(sys.stdin.buffer.readline())

def LS():
	return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()

def S():
	return sys.stdin.buffer.readline().rstrip().decode('utf-8')

def IR(n):
	return [I() for i in range(n)]

def LIR(n):
	return [LI() for i in range(n)]

def SR(n):
	return [S() for i in range(n)]

def LSR(n):
	return [LS() for i in range(n)]

def SRL(n):
	return [list(S()) for i in range(n)]

def MSRL(n):
	return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7
n = I()
x = LI() + [INF]
l = I()
q = I()
db = [[0] * n for _ in range(31)]
now = 0
for i in range(n):
	while x[i] + l >= x[now + 1]:
		now += 1
	db[0][i] = now
for j in range(1, 31):
	for k in range(n):
		db[j][k] = db[j - 1][db[j - 1][k]]
for _ in range(q):
	(a, b) = LI()
	if a > b:
		(a, b) = (b, a)
	a -= 1
	b -= 1
	ret = 0
	for kk in range(30, -1, -1):
		if db[kk][a] < b:
			a = db[kk][a]
			ret += 2 ** kk
	print(ret + 1)


def inpl():
	return [int(i) for i in input().split()]

def hmd(a, b):
	ctr = -1
	while H[ctr + 1][a] < b:
		ctr += 1
	vn = H[ctr][a]
	if vn == b and ctr == 0 or ctr == -1:
		return 1
	return 2 ** ctr + hmd(vn, b)
N = int(input())
x = inpl() + [10 ** 10]
L = int(input())
H = []
G = [N - 1] * N
b = 0
for a in range(N):
	while x[b + 1] - x[a] <= L:
		if b == N - 1:
			break
		b += 1
	G[a] = b
H.append(G)
while G[0] != N - 1:
	G = [G[i] for i in G]
	H.append(G)
H.append([10 ** 10] * N)
Q = int(input())
for _ in range(Q):
	(a, b) = sorted(inpl())
	print(hmd(a - 1, b - 1))


import sys
buff_readline = sys.stdin.buffer.readline
readline = sys.stdin.readline

def read_int():
	return int(buff_readline())

def read_int_n():
	return list(map(int, buff_readline().split()))

class Bisect:

	def __init__(self, func):
		self.__func = func

	def bisect_left(self, x, lo, hi):
		while lo < hi:
			mid = (lo + hi) // 2
			if self.__func(mid) < x:
				lo = mid + 1
			else:
				hi = mid
		return lo

	def bisect_right(self, x, lo, hi):
		while lo < hi:
			mid = (lo + hi) // 2
			if x < self.__func(mid):
				hi = mid
			else:
				lo = mid + 1
		return lo

class Doubling:

	def __init__(self, N, a0):
		self.N = N
		self.nt = [[None] * N for i in range(N.bit_length())]
		for (i, a) in enumerate(a0):
			self.nt[0][i] = a
		for i in range(1, len(self.nt)):
			for j in range(N):
				if self.nt[i - 1][j] is None:
					self.nt[i][j] = None
				else:
					self.nt[i][j] = self.nt[i - 1][self.nt[i - 1][j]]

	def apply(self, i, n):
		j = i
		for k in range(n.bit_length()):
			m = 1 << k
			if m & n:
				j = self.nt[k][j]
			if j is None:
				break
		return j

def slv(N, X, L, Q, AB):
	r = [0]
	for x in X:
		t = -1
		for j in range(r[-1], len(X)):
			if X[j] - x <= L:
				t = j
			else:
				break
		r.append(t)
	r.pop(0)
	d = Doubling(N, r)
	ans = []
	for (a, b) in AB:
		if a > b:
			(a, b) = (b, a)
		a -= 1
		b -= 1
		bisect = Bisect(lambda x: d.apply(a, x))
		i = bisect.bisect_left(b, 0, len(X) + 1)
		ans.append(i)
	return ans

def main():
	N = read_int()
	X = read_int_n()
	L = read_int()
	Q = read_int()
	AB = [read_int_n() for _ in range(Q)]
	print(*slv(N, X, L, Q, AB), sep='\n')
main()


from collections import defaultdict, deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random

def LI():
	return [int(x) for x in sys.stdin.readline().split()]

def I():
	return int(sys.stdin.readline())

def LS():
	return [list(x) for x in sys.stdin.readline().split()]

def S():
	res = list(sys.stdin.readline())
	if res[-1] == '\n':
		return res[:-1]
	return res

def IR(n):
	return [I() for i in range(n)]

def LIR(n):
	return [LI() for i in range(n)]

def SR(n):
	return [S() for i in range(n)]

def LSR(n):
	return [LS() for i in range(n)]
sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
	n = I()
	x = LI()
	L = I()
	q = I()
	p = [[] for i in range(n)]
	for i in range(n):
		xi = x[i]
		l = i
		r = n
		while r - l > 1:
			m = l + r >> 1
			xm = x[m]
			if xm - xi <= L:
				l = m
			else:
				r = m
		p[i].append(l)
	N = 20
	for j in range(N):
		for i in range(n):
			p[i].append(p[p[i][-1]][-1])
	for i in range(q):
		(a, b) = LI()
		a -= 1
		b -= 1
		(a, b) = (min(a, b), max(a, b))
		ans = 1
		for j in range(N)[::-1]:
			if p[a][j] < b:
				a = p[a][j]
				ans += 1 << j
		print(ans)
	return

def __starting_point():
	solve()
__starting_point()


N = int(input())
xs = list(map(int, input().split()))
L = int(input())
parent = [-1] * N
right = 0
for left in range(N):
	while right < N and xs[right] - xs[left] <= L:
		right += 1
	parent[left] = right - 1
ancestor = [parent]
for _ in range(N.bit_length() + 2):
	tmp = [ancestor[-1][anc] for anc in ancestor[-1]]
	ancestor.append(tmp)
Q = int(input())
answers = []
for _ in range(Q):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	if a == b:
		answers.append(0)
		continue
	if a > b:
		(a, b) = (b, a)
	ans = 0
	for k in range(len(ancestor) - 1, -1, -1):
		if ancestor[k][a] < b:
			ans += 1 << k
			a = ancestor[k][a]
	ans += 1
	answers.append(ans)
print(*answers, sep='\n')


from bisect import bisect_right
import sys
input = sys.stdin.readline
N = int(input())
x = list(map(int, input().split()))
L = int(input())
log = 1
while 1 << log < N:
	log += 1
doubling = [[0] * (log + 1) for _ in range(N)]
for i in range(N):
	j = bisect_right(x, x[i] + L) - 1
	doubling[i][0] = j
for l in range(1, log + 1):
	for i in range(N):
		doubling[i][l] = doubling[doubling[i][l - 1]][l - 1]
Q = int(input())
for _ in range(Q):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	if a > b:
		(a, b) = (b, a)
	ans = 0
	for l in range(log, -1, -1):
		if doubling[a][l] < b:
			ans += 1 << l
			a = doubling[a][l]
	print(ans + 1)


import bisect
n = int(input())
x = list(map(int, input().split()))
l = int(input())
q = int(input())
query = [list(map(int, input().split())) for i in range(q)]
log_size = n.bit_length() + 1
double = [[0] * n for i in range(log_size)]
for i in range(n):
	double[0][i] = bisect.bisect_right(x, x[i] + l) - 1
for k in range(1, log_size):
	for i in range(n):
		double[k][i] = double[k - 1][double[k - 1][i]]
for (a, b) in query:
	a -= 1
	b -= 1
	if a > b:
		(a, b) = (b, a)
	ans = 10 ** 18
	tmp = 0
	for k in range(log_size)[::-1]:
		if double[k][a] >= b:
			ans = min(ans, 2 ** k + tmp)
		else:
			a = double[k][a]
			tmp += 2 ** k
	print(ans)


import sys
input = lambda : sys.stdin.readline().rstrip()
N = int(input())
X = [int(a) for a in input().split()]
L = int(input())
NE = []
j = 0
for (i, x) in enumerate(X):
	while j < N - 1 and X[j + 1] <= x + L:
		j += 1
	NE.append(j)
D = [NE[:]]
for _ in range(16):
	d = D[-1]
	nd = [d[dd] for dd in d]
	D.append(nd)
Q = int(input())
for _ in range(Q):
	(a, b) = map(int, input().split())
	(a, b) = (a - 1, b - 1)
	if a > b:
		(a, b) = (b, a)
	re = 0
	s = a
	for i in range(17)[::-1]:
		d = D[i]
		if d[s] < b:
			s = d[s]
			re += 1 << i
	print(re + 1)


import bisect
import math
N = int(input())
x = list(map(int, input().split()))
L = int(input())
m = int(math.log(max(x), 2) + 1)
r = [[-1] * N for k in range(m)]
for i in range(N):
	base = x[i] + L
	p = bisect.bisect_right(x, base)
	r[0][i] = p - 1
for k in range(m - 1):
	for i in range(N):
		r[k + 1][i] = r[k][r[k][i]]

def isOK(mid):
	now = a
	pp = int(math.log(mid, 2) + 1)
	for i in range(pp):
		if mid >> i & 1:
			now = r[i][now]
	if now >= b:
		return True
	else:
		return False
Q = int(input())
for i in range(Q):
	(a, b) = map(int, input().split())
	(a, b) = (a - 1, b - 1)
	if a > b:
		(a, b) = (b, a)
	ng = 0
	ok = 2 ** m
	while abs(ok - ng) > 1:
		mid = int((ok + ng) / 2)
		if isOK(mid):
			ok = mid
		else:
			ng = mid
	print(ok)


import sys, bisect
input = sys.stdin.readline
N = int(input())
x = list(map(int, input().split()))
L = int(input())
doubling = [[-1 for i in range(N)] for j in range(20)]
for i in range(N):
	npos = x[i] + L
	index = bisect.bisect_right(x, npos)
	doubling[0][i] = index - 1
for i in range(1, 20):
	for j in range(N):
		doubling[i][j] = doubling[i - 1][doubling[i - 1][j]]
forward = [[-1 for i in range(N)] for j in range(20)]
for i in range(N):
	forward[0][i] = i
for i in range(1, 20):
	for j in range(N):
		forward[i][j] = doubling[i - 1][forward[i - 1][j]]
for _ in range(int(input())):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	if a > b:
		(a, b) = (b, a)
	res = 0
	for i in range(19, -1, -1):
		if b > forward[i][a]:
			a = doubling[i][a]
			res += 2 ** i
	print(res)


def main():
	n = int(input())
	x = list(map(int, input().split()))
	l = int(input())
	q = int(input())
	ab = [list(map(lambda x: int(x) - 1, input().split())) for _ in [0] * q]
	doubling = [[] for _ in [0] * n]
	j = 0
	for i in range(n):
		while j < n:
			if x[j] - x[i] > l:
				doubling[i].append(j - 1)
				break
			else:
				j += 1
	for i in range(n - 1, -1, -1):
		if not doubling[i]:
			doubling[i].append(n - 1)
		else:
			break
	for _ in range(16):
		for i in range(n):
			doubling[i].append(doubling[doubling[i][-1]][-1])
	for (a, b) in ab:
		if a > b:
			(a, b) = (b, a)
		ans = 0
		j = 16
		while j >= 0:
			if doubling[a][j] >= b:
				j -= 1
			else:
				a = doubling[a][j]
				ans += 2 ** j
		if a == b:
			print(ans)
		else:
			print(ans + 1)
main()


import bisect
import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
d = int(input())
graph = [[0 for i in range(n + 1)] for j in range(18)]
for i in range(n):
	x = bisect.bisect_right(a, a[i] + d)
	graph[0][i + 1] = x
for j in range(1, 18):
	for i in range(n):
		t = graph[j - 1][i + 1]
		graph[j][i + 1] = graph[j - 1][t]
q = int(input())
for _ in range(q):
	(x, y) = map(int, input().split())
	(x, y) = (min(x, y), max(x, y))
	ans = 0
	for j in range(18)[::-1]:
		if graph[j][x] < y:
			ans += 2 ** j
			x = graph[j][x]
		if j == 0 and x < y:
			ans += 1
	print(ans)


import sys
input = sys.stdin.readline
from bisect import *

def judge(a, b, x):
	now = a
	c = 0
	while x > 0:
		if x & 1:
			now = dp[c][now]
		x >>= 1
		c += 1
	return now >= b

def binary_search(a, b):
	(l, r) = (0, N - 1)
	while l <= r:
		m = (l + r) // 2
		if judge(a, b, m):
			r = m - 1
		else:
			l = m + 1
	return l
N = int(input())
x = list(map(int, input().split()))
L = int(input())
log_size = 22
dp = [[0] * N for _ in range(log_size)]
for i in range(N):
	dp[0][i] = bisect_right(x, x[i] + L) - 1
for i in range(1, log_size):
	for j in range(N):
		dp[i][j] = dp[i - 1][dp[i - 1][j]]
Q = int(input())
for _ in range(Q):
	(a, b) = map(int, input().split())
	(a, b) = (min(a, b) - 1, max(a, b) - 1)
	print(binary_search(a, b))


from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect

def LI():
	return [int(x) for x in sys.stdin.buffer.readline().split()]

def I():
	return int(sys.stdin.buffer.readline())

def LS():
	return [list(x) for x in sys.stdin.readline().split()]

def S():
	res = list(sys.stdin.readline())
	if res[-1] == '\n':
		return res[:-1]
	return res

def IR(n):
	return [I() for i in range(n)]

def LIR(n):
	return [LI() for i in range(n)]

def SR(n):
	return [S() for i in range(n)]

def LSR(n):
	return [LS() for i in range(n)]
sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
	n = I()
	x = LI()
	f = [[] for i in range(n)]
	l = I()
	for i in range(n):
		xi = x[i]
		j = bisect.bisect_right(x, l + xi) - 1
		f[i].append(j)
	h = int(math.log(n, 2)) + 1
	for j in range(h - 1):
		for i in range(n):
			f[i].append(f[f[i][j]][j])
	q = I()
	for _ in range(q):
		(a, b) = LI()
		a -= 1
		b -= 1
		if b < a:
			(a, b) = (b, a)
		ans = 0
		for i in range(h)[::-1]:
			if f[a][i] < b:
				a = f[a][i]
				ans += 1 << i
		print(ans + 1)
	return
solve()


from collections import defaultdict, deque
import sys, heapq, bisect, math, itertools, string, queue, datetime
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
mod = 10 ** 9 + 7

def inpl():
	return list(map(int, input().split()))

def inpls():
	return list(input().split())
N = int(input())
xx = inpl()
L = int(input())
K = N.bit_length()
db_r = [[0] * K for i in range(N)]
for (i, x) in enumerate(xx):
	ind = bisect.bisect_right(xx, x + L)
	db_r[i][0] = ind - 1
for k in range(1, K):
	for i in range(N):
		db_r[i][k] = db_r[db_r[i][k - 1]][k - 1]

def check(a, b, d):
	L = d.bit_length()
	for k in range(L):
		if d & 1 << k:
			a = db_r[a][k]
	return a >= b
Q = int(input())
for i in range(Q):
	(a, b) = inpl()
	a -= 1
	b -= 1
	(a, b) = (min(a, b), max(a, b))
	OK = N
	NG = 0
	while OK - NG > 1:
		mid = (OK + NG) // 2
		if check(a, b, mid):
			OK = mid
		else:
			NG = mid
	print(OK)


import sys

def input():
	return sys.stdin.readline().strip()

def mapint():
	return map(int, input().split())
sys.setrecursionlimit(10 ** 9)
N = int(input())
Xs = list(mapint())
L = int(input())
from bisect import bisect_right
nex = [[0] * N for _ in range(32)]
for i in range(N):
	now = Xs[i]
	idx = bisect_right(Xs, now + L) - 1
	nex[0][i] = idx
for i in range(1, 32):
	for j in range(N):
		nex[i][j] = nex[i - 1][nex[i - 1][j]]
Q = int(input())
for _ in range(Q):
	(a, b) = mapint()
	if a > b:
		(a, b) = (b, a)
	(a, b) = (a - 1, b - 1)
	cnt = 0
	for i in range(31, -1, -1):
		if nex[i][a] < b:
			cnt += 2 ** i
			a = nex[i][a]
	if a != b:
		cnt += 1
	print(cnt)


import sys
input = sys.stdin.readline
from bisect import bisect
N = int(input())
X = [int(i) for i in input().split()]
L = int(input())
Q = int(input())
T = []
for i in range(Q):
	(a, b) = map(int, input().split())
	if a > b:
		(a, b) = (b, a)
	T.append((a - 1, b - 1))
F = [0] * N
for i in range(N):
	F[i] = bisect(X, X[i] + L) - 1
dp = [[N - 1] * N for i in range(18)]
for i in range(N):
	dp[0][i] = F[i]
for c in range(1, 18):
	for i in range(N):
		dp[c][i] = dp[c - 1][dp[c - 1][i]]

def f(a, b):
	num = 0
	t = a
	while True:
		for i in range(18):
			if dp[i][t] >= b:
				s = i
				break
		if s == 0:
			num += 1
			break
		num += pow(2, s - 1)
		t = dp[s - 1][t]
	print(num)
for (a, b) in T:
	f(a, b)


from bisect import bisect
inpl = lambda : list(map(int, input().split()))
N = int(input())
X = inpl()
L = int(input())
Q = int(input())
R = [[0] * N for k in range(17)]
for i in range(N):
	R[0][i] = bisect(X, X[i] + L) - 1
for k in range(16):
	for i in range(N):
		R[k + 1][i] = R[k][R[k][i]]

def reach(a, d):
	O = format(d, 'b').zfill(17)[::-1]
	for k in range(16, -1, -1):
		if O[k] == '1':
			a = R[k][a]
	return a

def bisearch(a, b):
	(a, b) = (a - 1, b - 1)
	if b < a:
		(a, b) = (b, a)
	OK = b - a
	NG = 0
	while abs(OK - NG) > 1:
		mid = (OK + NG) // 2
		if reach(a, mid) >= b:
			OK = mid
		else:
			NG = mid
	return OK
print(*[bisearch(*inpl()) for _ in range(Q)], sep='\n')


from math import *
from bisect import *
(n, *t) = map(int, open(0).read().split())
m = int(log2(n)) + 1
x = t[:n]
l = t[n]
d = [[bisect(x, y + l) - 1 for y in x]] + [[0] * n for _ in range(m)]
for i in range(m):
	for j in range(n):
		d[i + 1][j] = d[i][d[i][j]]
for (a, b) in zip(t[n + 2::2], t[n + 3::2]):
	a -= 1
	b -= 1
	if b < a:
		(a, b) = (b, a)
	c = 1
	for i in range(m, -1, -1):
		if d[i][a] < b:
			a = d[i][a]
			c += 2 ** i
	print(c)


from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
from operator import mul
sys.setrecursionlimit(2147483647)
INF = 10 ** 20

def LI():
	return list(map(int, sys.stdin.buffer.readline().split()))

def I():
	return int(sys.stdin.buffer.readline())

def LS():
	return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()

def S():
	return sys.stdin.buffer.readline().rstrip().decode('utf-8')

def IR(n):
	return [I() for i in range(n)]

def LIR(n):
	return [LI() for i in range(n)]

def SR(n):
	return [S() for i in range(n)]

def LSR(n):
	return [LS() for i in range(n)]

def SRL(n):
	return [list(S()) for i in range(n)]

def MSRL(n):
	return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007
n = I()
X = LI()
l = I()
log_n = (n - 1).bit_length()
doubling = [[n] * n for _ in range(log_n)]
for i in range(n - 1):
	doubling[0][i] = bisect_right(X, X[i] + l) - 1
for j in range(1, log_n):
	for k in range(n):
		if doubling[j - 1][k] == n:
			continue
		doubling[j][k] = doubling[j - 1][doubling[j - 1][k]]
q = I()
for _ in range(q):
	(a, b) = LI()
	if a > b:
		(a, b) = (b, a)
	a -= 1
	b -= 1
	ans = 0
	for m in range(log_n - 1, -1, -1):
		if doubling[m][a] < b:
			a = doubling[m][a]
			ans += 2 ** m
	print(ans + 1)


import sys
sys.setrecursionlimit(10 ** 6)
from bisect import bisect_left, bisect
n = int(input())
x = list(map(int, input().split()))
L = int(input())
t = n.bit_length()
prv = [n - 1] * n
for i in range(n):
	prv[i] = bisect(x, x[i] + L) - 1
kprv = [prv]
S = prv
for i in range(t - 1):
	kar = [n - 1] * n
	for j in range(n):
		kar[j] = S[S[j]]
	kprv.append(kar)
	S = kar
q = int(input())
for _ in range(q):
	(a, b) = map(lambda x: int(x) - 1, input().split())
	if a > b:
		(a, b) = (b, a)
	lef = 0
	rig = n - 1
	while rig - lef > 1:
		mid = (rig + lef) // 2
		p = mid.bit_length()
		now = a
		for i in range(p):
			if mid >> i & 1 == 1:
				now = kprv[i][now]
		if now >= b:
			rig = mid
		elif now < b:
			lef = mid
	print(rig)


from bisect import bisect_left, bisect_right
N = int(input())
xs = list(map(int, input().split()))
L = int(input())
Q = int(input())
ABs = [tuple(map(lambda x: int(x) - 1, input().split())) for _ in range(Q)]
logN = (N - 1).bit_length()
parentss = [[N - 1] * (logN + 1) for _ in range(N)]
for i in range(N - 1):
	iL = bisect_right(xs, xs[i] + L)
	parentss[i][0] = iL - 1
for d in range(1, logN + 1):
	for i in range(N - 1):
		parentss[i][d] = parentss[parentss[i][d - 1]][d - 1]
anss = []
for (A, B) in ABs:
	if A > B:
		(A, B) = (B, A)
	i = A
	ans = 1
	for d in reversed(range(logN + 1)):
		if parentss[i][d] < B:
			i = parentss[i][d]
			ans += 2 ** d
	anss.append(ans)
print('\n'.join(map(str, anss)))


def main2(n, x, l, q, ab):
	ary = [[0] * n for _ in range(30)]
	idx = 1
	for i in range(n):
		while idx + 1 < n and x[idx + 1] - x[i] <= l:
			idx += 1
		ary[0][i] = idx
	for k in range(29):
		for i in range(n):
			if ary[k][i] < n:
				ary[k + 1][i] = ary[k][ary[k][i]]
			else:
				ary[k + 1][i] = n
	ret = []
	for (a, b) in ab:
		(a, b) = (a - 1, b - 1)
		if a > b:
			(a, b) = (b, a)
		tmp = 0
		k = 0
		while a < b:
			k = 0
			while ary[k + 1][a] < b:
				k += 1
			tmp += 1 << k
			a = ary[k][a]
		ret.append(tmp)
	return ret

def __starting_point():
	n = int(input())
	x = list(map(int, input().split()))
	l = int(input())
	q = int(input())
	ab = [list(map(int, input().split())) for _ in range(q)]
	ret2 = main2(n, x, l, q, ab)
	print(*ret2, sep='\n')
__starting_point()


def main():
	n = int(input())
	xs = [int(c) for c in input().split()]
	l = int(input())
	xs.append(10 ** 17)
	nexts = list(range(n))
	for fr in range(n):
		(p, q) = (fr, n)
		while q - p > 1:
			m = (p + q) // 2
			if xs[m] - xs[fr] <= l:
				p = m
			else:
				q = m
		nexts[fr] = p
	doubling = [nexts]
	for _ in range(20):
		base = doubling[-1]
		nexts = [base[base_next] for base_next in base]
		doubling.append(nexts)

	def query(fr, to):
		if fr >= to:
			return 0
		(p, q) = (0, 20)
		while q - p > 1:
			m = (p + q) // 2
			if doubling[m][fr] >= to:
				q = m
			else:
				p = m
		return query(doubling[p][fr], to) + 2 ** p
	q_count = int(input())
	for _ in range(q_count):
		(a, b) = map(int, input().split())
		if a > b:
			(a, b) = (b, a)
		a -= 1
		b -= 1
		print(query(a, b))

def __starting_point():
	main()
__starting_point()


import sys, queue, math, copy, itertools, bisect, collections, heapq

def main():
	LI = lambda : [int(x) for x in sys.stdin.readline().split()]
	_LI = lambda : [int(x) - 1 for x in sys.stdin.readline().split()]
	NI = lambda : int(sys.stdin.readline())
	N = NI()
	x = LI()
	L = NI()
	m = N.bit_length()
	f = [[N - 1] * N for _ in range(m)]
	j = 0
	for i in range(N - 1):
		while x[i] + L >= x[j + 1]:
			j += 1
			if j >= N - 1:
				break
		else:
			f[0][i] = j
			continue
		break
	for k in range(1, m):
		for i in range(N):
			f[k][i] = f[k - 1][f[k - 1][i]]
	for _ in range(NI()):
		ans = 0
		(a, b) = _LI()
		if a > b:
			(a, b) = (b, a)
		for k in range(m - 1, -1, -1):
			if f[k][a] < b:
				a = f[k][a]
				ans += 2 ** k
		print(ans + 1)

def __starting_point():
	main()
__starting_point()


import math
N = int(input())
X = list(map(int, input().split()))
L = int(input())
M = N.bit_length() + 3
doub = [[0 for _ in range(N)] for _ in range(M)]
r = 0
for l in range(N):
	db = doub[0]
	while r < N and X[r] <= X[l] + L:
		r += 1
	r -= 1
	db[l] = r
for i in range(1, M):
	db = doub[i]
	dbp = doub[i - 1]
	for l in range(N):
		db[l] = dbp[dbp[l]]

def db_query(a, b):
	ans = 0
	tmp = a
	d = N.bit_length()
	while d >= 0:
		if doub[d][tmp] < b:
			ans += pow(2, d)
			tmp = doub[d][tmp]
		d -= 1
	return ans + 1
Q = int(input())
for _ in range(Q):
	(a, b) = list(map(int, input().split()))
	if a > b:
		(a, b) = (b, a)
	a -= 1
	b -= 1
	print(db_query(a, b))


import os
import sys
import numpy as np
if os.getenv('LOCAL'):
	sys.stdin = open('_in.txt', 'r')
sys.setrecursionlimit(2147483647)
INF = float('inf')
IINF = 10 ** 18
MOD = 10 ** 9 + 7
N = int(sys.stdin.readline())
X = list(map(int, sys.stdin.readline().split()))
L = int(sys.stdin.readline())
Q = int(sys.stdin.readline())
AB = [list(map(int, sys.stdin.readline().split())) for _ in range(Q)]
N += 2
X = [X[0]] + X + [X[-1]]
X = np.array(X, dtype=int)
dp = np.zeros((N.bit_length() + 1, N), dtype=int)
dp[0] = np.searchsorted(X, X + L, side='right') - 1
for d in range(1, N.bit_length() + 1):
	dp[d] = dp[d - 1][dp[d - 1]]
dp = dp.tolist()

def solve(l, r):
	ret = 0
	d = len(dp) - 1
	while l + 1 < r:
		while d > 0 and dp[d][l] >= r:
			d -= 1
		ret += 1 << d
		l = dp[d][l]
	if l < r:
		ret += 1
	return ret
ans = []
for (a, b) in AB:
	ans.append(solve(min(a, b), max(a, b)))
print(*ans, sep='\n')


import bisect
n = int(input())
x = [int(item) for item in input().split()]
l = int(input())
q = int(input())
ab = []
for i in range(q):
	(a, b) = [int(item) for item in input().split()]
	a -= 1
	b -= 1
	if a > b:
		(a, b) = (b, a)
	ab.append((a, b))
dt = [[0] * n for _ in range(40)]
for (i, item) in enumerate(x):
	dt[0][i] = i
	dt[1][i] = bisect.bisect_right(x, item + l) - 1
for i in range(2, 40):
	for j in range(n):
		dt[i][j] = dt[i - 1][dt[i - 1][j]]
for (a, b) in ab:
	days = 0
	is_ok = False
	while a < b:
		for i in range(0, 40):
			if dt[i][a] >= b:
				if i == 1:
					days += 1
					is_ok = True
				else:
					a = dt[i - 1][a]
					days += 2 ** (i - 2)
				break
		if is_ok:
			break
	print(days)


def reachN(i0, n):
	if n == 0:
		return i0
	maxbit = ceil(log2(n))
	kL = []
	for i in range(maxbit + 1):
		if n >> i & 1:
			kL.append(i)
	i = i0
	for k in kL[::-1]:
		if start < goal:
			i = dp[k][i]
		else:
			i = dpInv[k][i]
	return i

def fun(n):
	if start < goal:
		return reachN(start, n) >= goal
	else:
		return reachN(start, n) <= goal

def binMin(l, r):
	if r - l == 1:
		return r
	m = (l + r) // 2
	if fun(m):
		r = m
	else:
		l = m
	return binMin(l, r)
import bisect
from math import log2, ceil
N = int(input())
xL = [-float('inf')] + [int(i) for i in input().split()]
Lmax = int(input())
kmax = ceil(log2(len(xL) - 2))
dp = [[len(xL) - 1] * (N + 1) for _ in range(kmax + 1)]
for i in range(1, N + 1):
	dp[0][i] = bisect.bisect_right(xL, xL[i] + Lmax) - 1
for k in range(1, kmax + 1):
	for i in range(1, N):
		dp[k][i] = dp[k - 1][dp[k - 1][i]]
dpInv = [[1] * (N + 1) for _ in range(kmax + 1)]
for i in range(N, 1, -1):
	dpInv[0][i] = bisect.bisect_left(xL, xL[i] - Lmax)
for k in range(1, kmax + 1):
	for i in range(N, 1, -1):
		dpInv[k][i] = dpInv[k - 1][dpInv[k - 1][i]]
Q = int(input())
for _ in range(Q):
	(start, goal) = list(map(int, input().split()))
	ans = binMin(0, abs(goal - start))
	print(ans)


class LCA:

	def __init__(self, graph, rootNode=0):
		self.graph = graph
		self.N = len(graph)
		self.Log_N = (self.N - 1).bit_length()
		self.rootNode = rootNode
		self.prev = [None] * self.N
		self.Depth = [-1] * self.N
		q = [self.rootNode]
		self.Depth[self.rootNode] = 0
		d = 0
		while q:
			qq = []
			d += 1
			for p in q:
				for np in self.graph[p]:
					if self.Depth[np] == -1:
						self.prev[np] = p
						self.Depth[np] = d
						qq.append(np)
			q = qq
		self.kprev = [self.prev]
		S = self.prev
		for k in range(self.Log_N):
			T = [None] * self.N
			for i in range(self.N):
				if S[i] is None:
					continue
				T[i] = S[S[i]]
			self.kprev.append(T)
			S = T

	def query(self, u, v):
		dd = self.Depth[v] - self.Depth[u]
		if dd < 0:
			(u, v) = (v, u)
			dd = -dd
		for k in range(self.Log_N + 1):
			if dd & 1:
				v = self.kprev[k][v]
			dd >>= 1
		if u == v:
			return u
		for k in reversed(range(self.Log_N)):
			pu = self.kprev[k][u]
			pv = self.kprev[k][v]
			if pu != pv:
				(u, v) = (pu, pv)
		return self.kprev[0][u]
import sys
input = sys.stdin.readline
from bisect import bisect_right
N = int(input())
A = list(map(int, input().split()))
L = int(input())
Q = int(input())
Query = [list(map(int, input().split())) for _ in range(Q)]
graph = [[] for _ in range(N)]
for (i, a) in enumerate(A):
	j = bisect_right(A, a + L) - 1
	graph[j].append(i)
	graph[i].append(j)
lca = LCA(graph, rootNode=N - 1)
for (a, b) in Query:
	d = 0
	a -= 1
	b -= 1
	if b < a:
		(a, b) = (b, a)
	for k in reversed(range(lca.Log_N)):
		nextnode = lca.kprev[k][a]
		if nextnode is None:
			continue
		elif nextnode == b:
			d += 1 << k
			break
		elif A[nextnode] < A[b]:
			d += 1 << k
			a = nextnode
	if nextnode != b:
		d += 1
	print(d)


import sys
import bisect

def solve():
	input = sys.stdin.readline
	mod = 10 ** 9 + 7
	n = int(input().rstrip('\n'))
	x = [v for v in list(map(int, input().rstrip('\n').split()))]
	l = int(input().rstrip('\n'))
	q = int(input().rstrip('\n'))
	ln = 64
	lsf = [[-1] * ln for _ in range(n)]
	lsb = [[-1] * ln for _ in range(n)]
	for i in range(n - 1):
		lsf[i][0] = bisect.bisect_right(x, x[i] + l) - 1
		lsb[-i - 1][0] = bisect.bisect_left(x, x[-i - 1] - l)
	for j in range(1, ln):
		for i in range(n):
			if lsf[i][j - 1] != -1:
				lsf[i][j] = lsf[lsf[i][j - 1]][j - 1]
			if lsb[i][j - 1] != -1:
				lsb[i][j] = lsb[lsb[i][j - 1]][j - 1]
	for i in range(q):
		(a, b) = list(map(int, input().rstrip('\n').split()))
		(a, b) = (a - 1, b - 1)
		cnt = 0
		if a < b:
			for j in range(b.bit_length(), -1, -1):
				if lsf[a][j] != -1:
					if lsf[a][j] <= b:
						cnt += 2 ** j
						a = lsf[a][j]
		else:
			for j in range(a.bit_length(), -1, -1):
				if lsb[a][j] != -1:
					if lsb[a][j] >= b:
						cnt += 2 ** j
						a = lsb[a][j]
		cnt += 0 if a == b else 1
		print(cnt)

def __starting_point():
	solve()
__starting_point()


N = int(input())
X = list(map(int, input().split()))
L = int(input())
from bisect import *

def get_move(X, L, left=False):
	res = [0] * N
	for i in range(N):
		if left:
			res[i] = bisect_left(X, X[i] - L)
		else:
			res[i] = bisect_right(X, X[i] + L) - 1
	K = N.bit_length()
	db = [[0] * N for _ in range(K)]
	db[0] = res
	for i in range(1, K):
		for j in range(N):
			db[i][j] = db[i - 1][db[i - 1][j]]
	return db

def search(dbr, dbl, a, b):
	if a > b:
		db = dbl
		left = True
	else:
		db = dbr
		left = False
	K = N.bit_length()
	ans = 0
	for p in range(K - 1, -1, -1):
		if left:
			if b < db[p][a]:
				a = db[p][a]
				ans += 1 << p
		elif b > db[p][a]:
			a = db[p][a]
			ans += 1 << p
	ans += 1
	return ans
dbr = get_move(X, L)
dbl = get_move(X, L, left=True)
Q = int(input())
ans = [0] * Q
for i in range(Q):
	(a, b) = map(int, input().split())
	ans[i] = search(dbr, dbl, a - 1, b - 1)
print(*ans, sep='\n')


from functools import reduce
from fractions import gcd
import math
import bisect
import itertools
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
INF = float('inf')

def main():
	N = int(input())
	x = list(map(int, input().split()))
	L = int(input())
	Q = int(input())
	LOG = 30
	nxt = [[-1] * N for _ in range(LOG)]
	for i in range(N):
		nxt[0][i] = bisect.bisect_left(x, x[i] + L + 1) - 1
	for k in range(LOG - 1):
		for i in range(N):
			if nxt[k][i] == -1:
				nxt[k + 1][i] = -1
			else:
				nxt[k + 1][i] = nxt[k][nxt[k][i]]
	for _ in range(Q):
		(a, b) = map(int, input().split())
		if a > b:
			(a, b) = (b, a)
		a -= 1
		b -= 1
		ans = 0
		for k in reversed(range(LOG)):
			if nxt[k][a] < b:
				a = nxt[k][a]
				ans += 2 ** k
		print(ans + 1)

def __starting_point():
	main()
__starting_point()


from bisect import *
r = range
(n, *t) = map(int, open(0).read().split())
x = t[:n]
d = [[bisect(x, y + t[n]) - 1 for y in x]] + [[0] * n for _ in r(16)]
for i in r(16):
	for j in r(n):
		d[i + 1][j] = d[i][d[i][j]]
for a in zip(t[n + 2::2], t[n + 3::2]):
	(a, b) = sorted((i - 1 for i in a))
	c = 1
	for i in r(16, -1, -1):
		if d[i][a] < b:
			a = d[i][a]
			c += 2 ** i
	print(c)


from bisect import bisect_left
INF = float('inf')

def check(a, b):
	(ng, ok) = (-1, N + 1)
	while ok - ng > 1:
		mid = (ng + ok) // 2
		now = a
		bit = 0
		x = mid
		while x:
			if x & 1:
				now = A[now][bit]
			bit += 1
			x >>= 1
		if b <= now:
			ok = mid
		else:
			ng = mid
	return ok
N = int(input())
x = list(map(int, input().split()))
K = N.bit_length() - 1
L = int(input())
A = [[INF] * (K + 1) for _ in range(N)]
for i in range(N):
	b = bisect_left(x, x[i] + L + 1)
	A[i][0] = b - 1
for k in range(K):
	for i in range(N):
		A[i][k + 1] = A[A[i][k]][k]
Q = int(input())
for _ in range(Q):
	(a, b) = map(lambda x: int(x) - 1, input().split())
	if a > b:
		(a, b) = (b, a)
	print(check(a, b))


import sys
sys.setrecursionlimit(10 ** 7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
from functools import partial, reduce
from operator import mul
prod = partial(reduce, mul)

def LI():
	return [int(x) for x in sys.stdin.readline().split()]

def LI_():
	return [int(x) - 1 for x in sys.stdin.readline().split()]

def LF():
	return [float(x) for x in sys.stdin.readline().split()]

def LS():
	return sys.stdin.readline().split()

def II():
	return int(sys.stdin.readline())

def SI():
	return input()
from bisect import bisect

def main():
	N = II()
	X = LI()
	X.append(INF)
	L = II()
	Q = II()
	AB = []
	for _ in range(Q):
		AB.append(LI_())
	Unreachs = [[] for _ in range(N)]
	for (i, x) in enumerate(X[:-1]):
		u = bisect(X, x + L)
		Unreachs[i].append(u)
	updated = True
	while updated:
		updated = False
		for i in range(N):
			u = Unreachs[Unreachs[i][-1] - 1][-1]
			updated = updated or u != Unreachs[i][-1]
			Unreachs[i].append(u)
	for (a, b) in AB:
		if a > b:
			(a, b) = (b, a)
		ans = 0
		while True:
			k = bisect(Unreachs[a], b) - 1
			if k < 0:
				ans += 1
				break
			ans += 2 ** k
			a = Unreachs[a][k] - 1
		print(ans)
	return 0
main()


N = int(input())
X = list(map(int, input().split()))
L = int(input())
Q = int(input())
V = [0] * N
ib = 0
for i in range(N):
	while X[i] - X[ib] > L:
		V[ib] = i - 1
		ib += 1
while ib != N - 1:
	V[ib] = N - 1
	ib += 1
dbl = [[0] * N for i in range(18)]
dbl[0] = V
for i in range(1, 18):
	for j in range(N):
		ii = dbl[i - 1][j]
		if ii == 0:
			break
		dbl[i][j] = dbl[i - 1][ii]
for i in range(Q):
	(a, b) = map(int, input().split())
	(a, b) = sorted([a, b])
	a -= 1
	b -= 1
	ind = a
	ans = 0
	for j in range(17, -1, -1):
		if dbl[j][ind] == 0:
			continue
		if dbl[j][ind] > b:
			continue
		if dbl[j][ind] == b:
			ans |= 1 << j
			break
		else:
			ans |= 1 << j
			ind = dbl[j][ind]
	else:
		ans += 1
	print(ans)


import math
import itertools
import heapq
from sys import stdin, stdout, setrecursionlimit
from bisect import bisect, bisect_left, bisect_right
from collections import defaultdict, deque

def LM(t, r):
	return list(map(t, r))

def R():
	return stdin.readline()

def RS():
	return R().split()

def I():
	return int(R())

def F():
	return float(R())

def LI():
	return LM(int, RS())

def LF():
	return LM(float, RS())

def ONE_SL():
	return list(input())

def ONE_IL():
	return LM(int, ONE_SL())

def ALL_I():
	return map(int, stdin)

def ALL_IL():
	return LM(int, stdin)

def ap(f):
	return f.append

def pll(li):
	print('\n'.join(LM(str, li)))

def pljoin(li, s):
	print(s.join(li))

def main():
	N = I()
	X = LI()
	L = I()
	Q = I()
	r = [[0 for _ in range(100010)] for _ in range(20)]
	for i in range(N):
		r[0][i] = bisect_right(X, X[i] + L) - 1
	for i in range(1, 20):
		for j in range(N):
			r[i][j] = r[i - 1][r[i - 1][j]]
	for q in range(Q):
		(a, b) = LI()
		a -= 1
		b -= 1
		if a > b:
			(a, b) = (b, a)
		ans = 0
		now = a
		for i in range(0, 20)[::-1]:
			if r[i][now] < b:
				now = r[i][now]
				ans += 2 ** i
		print(ans + 1)
main()


import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 9)
from bisect import bisect
n = int(input())
x = list(map(int, input().split()))
l = int(input())
depth = [-1] * n
depth[-1] = 0
m = 20
par = [[-1] * n for i in range(m)]

def dfs(i):
	if depth[i] >= 0:
		return depth[i]
	j = bisect(x, x[i] + l) - 1
	if j == n:
		j = n - 1
	par[0][i] = j
	depth[i] = dfs(j) + 1
	return depth[i]
for i in range(n):
	dfs(i)
for i in range(m - 1):
	for j in range(n):
		par[i + 1][j] = par[i][par[i][j]]

def hoge(x, y):
	k = 0
	for i in range(m)[::-1]:
		if 0 <= par[i][x] < y:
			k += 1 << i
			x = par[i][x]
	return k + 1
q = int(input())
ans = []
for i in range(q):
	(a, b) = map(int, input().split())
	(a, b) = (a - 1, b - 1)
	if a > b:
		(a, b) = (b, a)
	ans.append(hoge(a, b))
print(*ans, sep='\n')


import math
from bisect import bisect_left, bisect_right
N = int(input())
X = list(map(int, input().split()))
L = int(input())
Q = int(input())
Y = [list(map(int, input().split())) for _ in range(Q)]
LOGN = int(math.log(N) / math.log(2)) + 1
parent = [[-1] * N for _ in range(LOGN + 1)]
for k in range(LOGN + 1):
	for i in range(N):
		if k == 0:
			parent[k][i] = bisect_right(X, X[i] + L) - 1
		else:
			parent[k][i] = parent[k - 1][parent[k - 1][i]]

def find(a, b):
	num = 0
	u = a
	while True:
		k = 0
		for i in range(LOGN + 1):
			if parent[i][u] >= b:
				k = i
				break
		if k == 0:
			num += 1
			break
		num += pow(2, k - 1)
		u = parent[k - 1][u]
	return num
for (a, b) in Y:
	a -= 1
	b -= 1
	if a > b:
		(a, b) = (b, a)
	print(find(a, b))


import sys
input = sys.stdin.buffer.readline
import bisect
INF = float('inf')
from collections import defaultdict

def getlist():
	return list(map(int, input().split()))

def main():
	N = int(input())
	X = getlist()
	X.append(INF)
	L = int(input())
	double = [[0] * (N + 1) for i in range(20)]
	for i in range(N):
		p = bisect.bisect_left(X, X[i] + L + 1)
		double[0][i] = p - 1
	for i in range(20):
		double[i][N] = INF
	for i in range(1, 20):
		for j in range(N):
			double[i][j] = double[i - 1][double[i - 1][j]]
	Q = int(input())
	for i in range(Q):
		(a, b) = sorted(getlist())
		a -= 1
		b -= 1
		ans = 0
		for j in range(20):
			if double[19 - j][a] < b:
				a = double[19 - j][a]
				ans += 1 << 19 - j
		print(ans + 1)
main()


from bisect import *

class Doubling:

	def __init__(self, A, K_max, decrement=True):
		self.k_max = K_max.bit_length()
		self.n = len(A)
		self.decrement = decrement
		self.doubling = [[-1] * self.n for _ in range(self.k_max)]
		for (i, a) in enumerate(A):
			self.doubling[0][i] = a - self.decrement
		for i in range(1, self.k_max):
			for k in range(self.n):
				if self.doubling[i - 1][k] != -1:
					self.doubling[i][k] = self.doubling[i - 1][self.doubling[i - 1][k]]

	def apply(self, start, K):
		i = start - self.decrement
		for k in range(K.bit_length()):
			m = 1 << k
			if m & K:
				i = self.doubling[k][i]
			if i is None:
				break
		return i + self.decrement

def binary_search_int(ok, ng, test, a, b):
	while abs(ok - ng) > 1:
		mid = (ok + ng) // 2
		if test(mid, a, b):
			ok = mid
		else:
			ng = mid
	return ok
import sys
input = sys.stdin.readline
N = int(input())
X = list(map(int, input().split()))
L = int(input())
Q = int(input())
A = []
for x in X:
	i = bisect_left(X, x + 1 + L)
	A.append(i - 1)
doubling = Doubling(A, N + 1, decrement=False)

def test(x, a, b):
	return X[doubling.apply(a, x)] < X[b]
for _ in range(Q):
	(a, b) = map(int, input().split())
	(a, b) = (a - 1, b - 1)
	if a > b:
		(a, b) = (b, a)
	print(binary_search_int(0, N, test, a, b) + 1)