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

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

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

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

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

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

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

Solution (Python):
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_l = [[] for _ in range(n)]
dbl_r = [[] for _ in range(n)]
for dbl,xx in zip([dbl_l,dbl_r],[x,x[::-1]]):
    j = 0
    for i in range(n):
        while(j < n-1):
            if(abs(xx[j+1] - xx[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,dbl):
    if(dbl[a][0] >= b):
        return 1
    ind = bisect.bisect_left(dbl[a],b) - 1
    return 2**ind + calc(dbl[a][ind],b,dbl)

ans = []
it = iter(ab)
for a,b in zip(it,it):
    a -= 1
    b -= 1
    if(a<b):
        ans.append(calc(a,b,dbl_l))
    else:
        a,b = n-1-a,n-1-b
        ans.append(calc(a,b,dbl_r))

print('\n'.join(map(str,ans)))

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

Solution (Python):
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
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")
    for k in range(len(dl)-1, -1, -1):
        if dl[k][a]<b:
            a = dl[k][a]
            res += pow(2,k)



        else:
            tmp = min(tmp, res+pow(2,k))
    ans[i] = tmp
write("\n".join(map(str, ans)))

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

Solution (Python):


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
"""
L = [[bisect_left(x,i-l) for i in x]]
for i in range(M):
    LL = [L[-1][L[-1][i]] for i in range(n)]
    L.append(LL)

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

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

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

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



if __name__ == '__main__':
    main()

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



if __name__ == '__main__':
    main()

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

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

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

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

Solution (Python):
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)
if __name__ == "__main__":
  main()

Solution (Python):
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]]
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)
    if a == b:
      break
  print(res)

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

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



if __name__ == '__main__':
    main()

Solution (Python):

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


if __name__ == '__main__':
    main()

Solution (Python):

from functools import lru_cache
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')


if __name__ == '__main__':
    main()

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

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

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