Problem:
 Score : 700 points    Problem Statement 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 1 9
1 3 6 13 15 18 19 29 31
10
4
1 8
7 3
6 7
8 5      Sample Output 1 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 .

Solution (Python):
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)

Solution (Python):
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).tolist())
for i in range(U):
    next_x.append([next_x[i][next_x[i][n]] for n in range(N)])

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))

Solution (Python):
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))

Solution (Python):
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")

Solution (Python):
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)))

Solution (Python):

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)


if __name__ == '__main__':
    main()

Solution (Python):
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()

Solution (Python):

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


if __name__ == "__main__":
    C()

Solution (Python):

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


if __name__ == "__main__":
    C()

Solution (Python):
from bisect import bisect
import sys

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, sys.stdin.readline().strip().split())
	print(search(min(a, b)-1, max(a, b)-1))

Solution (Python):
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)

Solution (Python):
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))

Solution (Python):
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))

Solution (Python):
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
	while True:
		for i in range(18):
			if r[i][cur] >= y:
				if i == 0:
					return res+1
				cur = r[i-1][cur]
				res += 1 << (i-1) 
				break

for _ in range(q):
	a, b = map(int, input().split())
	print(search(min(a, b)-1, max(a, b)-1))

Solution (Python):
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
	while True:
		for i in range(18):
			if r[i][cur] >= y:
				if i == 0:
					return res+1
				cur = r[i-1][cur]
				res += 1 << (i-1) 
				break

for _ in range(q):
	a, b = map(int, input().split())
	print(search(min(a, b)-1, max(a, b)-1))

Solution (Python):
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)

Solution (Python):
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))

Solution (Python):
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))

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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')

Solution (Python):
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)

Solution (Python):
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))


if __name__ == '__main__':
    main()

Solution (Python):

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')

Solution (Python):
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)



if __name__ == '__main__':
	main()

Solution (Python):
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)

Solution (Python):
import bisect
import sys
import math
import itertools
sys.setrecursionlimit(10000)

INF = float('inf')


def i():
    return int(raw_input())
def ii():
    return map(int,raw_input().split(" "))
def s():
    return raw_input()
def ss():
    return raw_input().split(" ")
def slist():
    return list(raw_input())
def join(s):
    return ''.join(s)



n=i()
x=ii()
l=i()
q=i()
a,b=[0]*q,[0]*q
for j in range(q):
    aa,bb=ii()
    a[j],b[j]=min(aa,bb)-1,max(aa,bb)-1
table=[[0 for i in range(n)] for j in range(32)]


for k in range(n):
    table[0][k]=bisect.bisect_right(x,x[k]+l)-1
for j in range(1,32):
    for k in range(n):
        table[j][k]=table[j-1][table[j-1][k]]
for j in range(q):
    day=0
    cur=a[j]
    for k in reversed(range(32)):
        if table[k][cur]<b[j]:
            day+=2**k
            cur=table[k][cur]
    print day+1

Solution (Python):
import bisect

n=int(raw_input())
x=map(int,raw_input().split())+[float('inf')]
l=int(raw_input())
q=int(raw_input())
r=[[0]*20 for _ in xrange(n)]

for i in xrange(n):
    if x[i]+l==x[bisect.bisect_left(x,x[i]+l)]:
        r[i][0]=bisect.bisect_left(x,x[i]+l)
    else:
        r[i][0]=bisect.bisect_left(x,x[i]+l)-1

for k in xrange(19):
    for i in xrange(n):
        r[i][k+1]=r[r[i][k]][k]
        
for i in xrange(q):
    a,b=map(int,raw_input().split())
    a-=1
    b-=1
    ans=0
    if a>b:
        a,b=b,a
    while 1:
        if bisect.bisect_left(r[a],b)>=1:
            ans+=1<<(bisect.bisect_left(r[a],b)-1)
            a=r[a][bisect.bisect_left(r[a],b)-1]
        else :
            ans+=1<<bisect.bisect_left(r[a],b)
            break
    print(ans)