CodeEff/ECCO huggingface dataset:
# Original solution
# coding: utf-8
import sys
from functools import lru_cache
sys.setrecursionlimit(10 ** 9)

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
A = lr()
# 奇数の時と偶数の時、奇数の場合は真ん中を選ぶかどうか
INF = 10 ** 17

@lru_cache(None)
def F(index, n):
    if index >= N:
        return -INF
    if n == 0:
        return 0
    elif n == 1:
        return max(A[index:])
    ret = max(A[index] + F(index+2, n-1), F(index+1, n))
    return ret

answer = F(0, N//2)
print(answer)


# Optimized solution
# coding: utf-8
import sys
from functools import lru_cache
sys.setrecursionlimit(10 ** 9)

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
A = lr()
# 奇数の時と偶数の時、奇数の場合は真ん中を選ぶかどうか
INF = 10 ** 17

@lru_cache(None)
def F(index, n):
    if index >= N:
        return -INF
    if N - index + 2 < 2 * n:
        return -INF
    if n == 0:
        return 0
    elif n == 1:
        return max(A[index:])
    ret = max(A[index] + F(index+2, n-1), F(index+1, n))
    return ret

answer = F(0, N//2)
print(answer)
# Original solution
# coding: utf-8
import sys
from functools import lru_cache
sys.setrecursionlimit(10 ** 9)

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
A = lr()
INF = 10 ** 17

def F(index, n):
    if index >= N:
        return -INF
    if N - index + 2 < 2 * n:
        return -INF
    if n == 0:
        return 0
    elif n == 1:
        return max(A[index:])
    ret = max(A[index] + F(index+2, n-1), F(index+1, n))
    return ret

answer = F(0, N//2)
print(answer)


# Optimized solution
# coding: utf-8
import sys
from functools import lru_cache
sys.setrecursionlimit(10 ** 9)

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
A = lr()
INF = 10 ** 17

@lru_cache(None)
def F(index, n):
    if index >= N:
        return -INF
    if N - index < 2 * n - 1:
        return -INF
    if n == 0:
        return 0
    elif n == 1:
        return max(A[index:])
    ret = max(A[index] + F(index+2, n-1), F(index+1, n))
    return ret

answer = F(0, N//2)
print(answer)
# Original solution
from collections import deque, Counter
from itertools import chain, combinations
import json
# import numpy as np
import bisect
import sys
import math
import bisect

sys.setrecursionlimit(10 ** 8)

M = 10 ** 9 + 7


def main():
    N = int(eval(input()))
    A = [int(a) for a in input().split()]

    DP = [[0] * (N + 1) for _ in range(N + 1)]
    DP[1][1] = A[0]

    for i in range(2, N + 1):
        a = math.floor((i - 1) / 2)
        b = math.floor((i + 1) / 2)
        for j in range(a, b + 1):
            DP[i][j] = max(DP[i - 1][j], DP[i - 2][j - 1] + A[i - 1])
    print((int(DP[N][math.floor(N / 2)])))


if __name__ == "__main__":
    main()


# Optimized solution
from collections import deque, Counter, defaultdict
from itertools import chain, combinations
import json
# import numpy as np
import bisect
import sys
import math
import bisect
from functools import lru_cache

sys.setrecursionlimit(10 ** 8)

M = 10 ** 9 + 7
INF = 10 ** 17


def main():
    N = int(eval(input()))
    A = [int(a) for a in input().split()]

    @lru_cache()
    def f(i, j):
        if i < 0 or j < 0:
            return -INF
        if i == 0:
            return -INF
        if j == 0:
            return 0
        if j == 1:
            return max(A[:i])
        return max(A[i - 1] + f(i - 2, j - 1), f(i - 1, j))

    print((f(N, math.floor(N / 2))))


if __name__ == "__main__":
    main()
# Original solution
from collections import deque, Counter, defaultdict
from itertools import chain, combinations
import json
# import numpy as np
import bisect
import sys
import math
import bisect
from functools import lru_cache

sys.setrecursionlimit(10 ** 8)

M = 10 ** 9 + 7
INF = 10 ** 17


def main():
    N = int(eval(input()))
    A = [int(a) for a in input().split()]

    @lru_cache(None)
    def f(i, j):
        if i < 0 or j < 0:
            return -INF
        if i == 0:
            return -INF
        if j == 0:
            return 0
        if j == 1:
            return max(A[:i])
        return max(A[i - 1] + f(i - 2, j - 1), f(i - 1, j))

    print((f(N, math.floor(N / 2))))


if __name__ == "__main__":
    main()


# Optimized solution
from collections import deque, Counter, defaultdict
from itertools import chain, combinations
import json
# import numpy as np
import bisect
import sys
import math
import bisect
from functools import lru_cache

sys.setrecursionlimit(10 ** 8)

M = 10 ** 9 + 7
INF = 10 ** 17


def main():
    N = int(eval(input()))
    A = [int(a) for a in input().split()]

    @lru_cache(None)
    def f(i, j):
        if i < 0 or j < 0:
            return -INF
        if i == 0:
            return -INF
        if abs(j - i // 2 - 1) >= 2:
            return -INF
        if j == 0:
            return 0
        if j == 1:
            return max(A[:i])
        return max(A[i - 1] + f(i - 2, j - 1), f(i - 1, j))

    print((f(N, math.floor(N / 2))))


if __name__ == "__main__":
    main()
# Original solution
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate
import sys
import bisect
import string
import math
import time


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


def S(): return eval(input())


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


def MS(): return list(map(str, input().split()))


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


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


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


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


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


yn = {False: 'No', True: 'Yes'}
YN = {False: 'NO', True: 'YES'}
MOD = 10**9+7
inf = float('inf')
IINF = 10**10
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']

show_flg = False
# show_flg = True


def main():
    N = I()
    a = LI()
    dp = [0] * N
    dp[1] = max(a[0], a[1])
    c = a[0]

    for i in range(2, N):
        if i % 2 == 0:
            c += a[i]
            dp[i] = max(dp[i-2] + a[i], dp[i-1])
        else:
            dp[i] = max(dp[i-2] + a[i], c)

    print((dp[-1]))


if __name__ == '__main__':
    main()


# Optimized solution
n = int(eval(input()))
A = list(map(int, input().split()))
INF = 10**18
dp_use = [-INF] * 5
dp_not_use = [-INF] * 5
dp_not_use[0] = 0
 
for a in A:
    tmp_use = [-INF] * 5
    tmp_not_use = [-INF] * 5
    for current_dif in range(-3,2):
        if current_dif-1 >= -3:
            tmp_use[current_dif] = dp_not_use[current_dif - 1] + a
        if current_dif+1 < 2:
            tmp_not_use[current_dif] = max(dp_use[current_dif+1], dp_not_use[current_dif+1])
    dp_use = tmp_use
    dp_not_use = tmp_not_use
dif = n//2 - (n-n//2)
print((max(dp_use[dif], dp_not_use[dif])))
# Original solution
n = int(eval(input()))
a = list(map(int, input().split()))
if n % 2 == 0:
    ans, cnt = 0, 0
    for i in range(n):
        if i % 2 == 1:
            ans += a[i]
            cnt += a[i]
    for i in range(n):
        if i % 2 == 0:
            cnt += a[i]
        else:
            cnt -= a[i]
            ans = max(cnt, ans)
else:
    a.insert(0, 0)
    dp = [[0] * (n + 1) for _ in range(3)]
    for i in range(3):
        for j in range(1 + i, n + i - 1, 2):
            if i == 0:
                if j == 1:
                    dp[i][j] = a[j]
                else:
                    dp[i][j] = dp[i][j - 2] + a[j]
            else:
                dp[i][j] = max(dp[i - 1][j - 1], dp[i][j - 2] + a[j])
    ans = dp[2][n]
print(ans)

# Optimized solution
n = int(eval(input()))
a = list(map(int, input().split()))
a.insert(0, 0)
dp = [[0] * (n + 1) for _ in range(3)]
for i in range(n % 2 + 2):
    for j in range(1 + i, n + i, 2):
        if i == 0:
            if j == 1:
                dp[i][j] = a[j]
            else:
                dp[i][j] = dp[i][j - 2] + a[j]
        else:
            dp[i][j] = max(dp[i - 1][j - 1], dp[i][j - 2] + a[j])
ans = dp[n % 2 + 1][n]
print(ans)
# Original solution
n,*l=list(map(int,open(0).read().split()));p=[0]*n;d=p[:]
for i,l in enumerate(l):p[i]+=l+p[i-2];d[i]=max(l+d[i-2],[d,p][i&1][i-1])
print((d[-1]))

# Optimized solution
n,*l=list(map(int,open(0).read().split()));p=[0]*n;d=p[:]
for i,l in enumerate(l):p[i]=l+p[i-2];d[i]=max(l+d[i-2],[d,p][i&1][i-1])
print((d[-1]))
# Original solution
n,*l=list(map(int,open(0).read().split()))
p=0,0
d=p
i=0
for l in l:d+=max(l+d[-2],[d,p][i&1][-1]),;p+=l+p[-2],;i+=1
print((d[-1]))

# Optimized solution
n,*l=list(map(int,open(0).read().split()))
p=[0,0]
d=[0,0]
i=0
for l in l:d+=max(l+d[-2],[d,p][i&1][-1]),;p+=l+p[-2],;i+=1
print((d[-1]))
# Original solution
from sys import stdin
import sys
# sys.setrecursionlimit(10**8)

def nextLine(): return next(stdin)
def nextStrList(): return nextLine().split()
def nextIntList(): return [int(_) for _ in nextStrList()]


def main():
	n=int(nextLine())
	aList=nextIntList()
	
	num=n//2
	score=[[None for _ in range(num)] for i in range(n)]
	
	for i in range(n):
		
		if i==0:
			score[i][0]=aList[i]
		else:
			score[i][0]=max(aList[i], score[i-1][0])
			
		for j in range(1, num):
			nextScore=[]
			if i>=1:
				s=score[i-1][j]
				if s is not None:
					nextScore.append(s)
			if i>=2:
				s=score[i-2][j-1]
				if s is not None:
					s+=aList[i]
					nextScore.append(s)
			if len(nextScore)>0:
				nextScore=max(nextScore)
				score[i][j]=nextScore
	
# 		print(i, *[str(s) for s in score[i]], sep="\t")
	
	print((score[-1][-1]))
	
if __name__=="__main__":
	main()


# Optimized solution
from sys import stdin
import sys
# sys.setrecursionlimit(10**8)

def nextLine(): return next(stdin)
def nextStrList(): return nextLine().split()
def nextIntList(): return [int(_) for _ in nextStrList()]

# def comp0(n, aList):
# 	num=n//2
# 	score=[[None for _ in range(num)] for i in range(n)]
# 	
# 	for i in range(n):
# 		
# 		if i==0:
# 			score[i][0]=aList[i]
# 		else:
# 			score[i][0]=max(aList[i], score[i-1][0])
# 			
# 		for j in range(1, num):
# 			nextScore=[]
# 			if i>=1:
# 				s=score[i-1][j]
# 				if s is not None:
# 					nextScore.append(s)
# 			if i>=2:
# 				s=score[i-2][j-1]
# 				if s is not None:
# 					s+=aList[i]
# 					nextScore.append(s)
# 			if len(nextScore)>0:
# 				nextScore=max(nextScore)
# 				score[i][j]=nextScore
# 	
# # 		print(i, aList[i], *[str(s) for s in score[i]], sep="\t")
# 	
# 	print(score[-1][-1])
	
	
def comp(n, aList):
	num=n//2
	score=[[None for _ in range(num)] for i in range(3)]
# 	base=[0 for _ in range(num)]
	
	for i in range(n):
		for j in range(max(0, num-(n-i)//2-1), min(i//2+1,num)):
			if j==0:
				if i==0:
					ns=aList[i]
				else:
					ns=max(aList[i], score[(i-1)%3][0])
			else:
				nextScore=[]
				if i>=1:
					s=score[(i-1)%3][j]
					if s is not None:
						nextScore.append(s)
				if i>=2:
					s=score[(i-2)%3][j-1]
					if s is not None:
						s+=aList[i]
						nextScore.append(s)
				if len(nextScore)>0:
					ns=max(nextScore)
			
			score[i%3][j]=ns
	
# 		print(i, *[str(s) for s in score[i%3]], sep="\t")
	
	print((score[(n-1)%3][-1]))


def main():
	n=int(nextLine())
	aList=nextIntList()

# 	import numpy as np
# 	n=200000
# # 	aList=list(np.random.randint(-1000000000, 1000000001, n))
# # 	n=22
# 	aList=list(np.random.randint(-9, 10, n))
	
	comp(n, aList)
# 	comp0(n, aList)
	
	
if __name__=="__main__":
	main()
# Original solution
import sys

N = int(eval(input()))
A = list(map(int,input().split()))

INF = 10**20
dp = [[[-INF]*2 for _ in range(2)] for _ in range(N+1)]


if N&1:
    dp[0][1][0] = 0
    for i in range(N):
        if i&1:
            dp[i+1][0][0] = max(dp[i][0][0], dp[i][0][1])
            dp[i+1][1][0] = max(dp[i][1][0], dp[i][1][1])
            dp[i+1][1][1] = dp[i][0][0] + A[i]

        else:
            dp[i+1][0][0] = max(dp[i][1][0], dp[i][1][1])
            dp[i+1][0][1] = dp[i][0][0] + A[i]
            dp[i+1][1][1] = dp[i][1][0] + A[i]

    ans = max(dp[N][0][0], dp[N][0][1])            

else:
    dp[0][1][0] = 0
    for i in range(N):
        if i&1:
            dp[i+1][1][0] = dp[i][1][1]
            dp[i+1][1][1] = dp[i][0][0] + A[i]            

        else:
            dp[i+1][0][0] = max(dp[i][1][0], dp[i][1][1])
            dp[i+1][1][1] = dp[i][1][0] + A[i]
    ans = max(dp[N][1][0], dp[N][1][1])

print(ans)

# Optimized solution
import sys
input = sys.stdin.readline

n = int(eval(input()))
a = list(map(int,input().split()))

dp = [0]*n
c = a[0]
dp[1] = max(a[0],a[1])

for i in range(2,n):
    if i%2 == 0:
        c += a[i]
        dp[i] = max(dp[i-2]+a[i],dp[i-1])
    else:
        dp[i] = max(dp[i-2]+a[i],c)

print((dp[-1]))
# Original solution
from collections import defaultdict
n = int(eval(input()))
m = n//2
INF = 10**18
dp = [defaultdict(lambda: -INF)for _ in range(n+2)]
for i, a in enumerate(map(int, input().split()), 2):
    for j in range(1, -(-i//2)+1):
        if j-1 == 0:
            dp[i-2][j-1] = 0
        dp[i][j] = max(dp[i-1][j], dp[i-2][j-1]+a)

print((dp[n+1][m]))


# Optimized solution
from collections import defaultdict
n = int(eval(input()))
m = n//2
INF = 10**18
dp = [defaultdict(lambda: -INF)for _ in range(n+2)]
for i, a in enumerate(map(int, input().split()), 2):
    for j in range(max(1, i//2-1), -(-i//2)+1):
        if j-1 == 0:
            dp[i-2][j-1] = 0
        dp[i][j] = max(dp[i-1][j], dp[i-2][j-1]+a)

print((dp[n+1][m]))
# Original solution
n = int(eval(input()))
a = list(map(int,input().split()))
dp = [[0 for i in range(3)] for j in range(n+1)]
for i in range(1,n+1):
  ai = a[i-1]
  dp[i] = dp[i-1][:]
  if i%2:
    dp[i][0] += +ai
    dp[i][1] = max(dp[i-1][0],dp[i-1][1])
  if i%2 == 0:
    dp[i][1] += ai
    dp[i][2] = max(dp[i-1][1],dp[i-1][2])
  if i >= 3 and i%2:
    dp[i][2] += ai
if n%2 == 0:
  print((max(dp[-1][0],dp[-1][1])))
else:
  print((max(dp[-1][1],dp[-1][2])))

# Optimized solution
n = int(eval(input()))
a = list(map(int,input().split()))
dp = [0 for i in range(3)]
for i in range(1,n+1):
  ai = a[i-1]
  if i%2:
    dp[1] = max(dp[0],dp[1])
    dp[0] += ai
  if i%2 == 0:
    dp[2] = max(dp[1],dp[2])
    dp[1] += ai
  if i >= 3 and i%2:
    dp[2] += ai
if n%2 == 0:
  print((max(dp[0],dp[1])))
else:
  print((max(dp[1],dp[2])))
# Original solution
import sys
sys.setrecursionlimit(10**9)

N = int(eval(input()))
A = list(map(int, input().split()))

def solve_even(a, n):
  s = sum(a[::2])
  ans = s
  i = n - 2
  while i >= 0:
    s += a[i+1] - a[i]
    ans = max(ans, s)
    i -= 2
  return ans

def solve_odd(a, n):
  if n == 1:
    return 0
  ans = solve_even(a[:-1], n-1)
  s = a.pop()
  a.pop()
  ans = max(ans, s + solve_odd(a, n-2))
  return ans
  

if N%2 == 0:
  print((solve_even(A, N)))
else:
  print((solve_odd(A, N)))

# Optimized solution
N = int(eval(input()))
A = list(map(int, input().split()))

dp = [0] * (N + 1)
dp[2] = max(A[0], A[1])
s = A[0]
for i, a in enumerate(A, 1):
  if i <= 2:
    continue
  if i%2: # 奇数
    dp[i] = max(dp[i-1], a+dp[i-2])
    s += a
  else: # 偶数
    dp[i] = max(a+dp[i-2], s)

print((dp[-1]))
# Original solution
import math
import sys
sys.setrecursionlimit(1000000)

N = int(eval(input()))
A = [int(i) for i in input().split()]

memo = {}
def sub_max(n, m):
    if((n, m) in memo):
        return memo[(n, m)]
    
    if(m == 1 and n >= 1):
        memo[(n, m)] = max(A[-n:])
        return memo[(n, m)]

    if(m >= n):
        memo[(n, m)] = -float('inf')
        return -float('inf')
    
    res = -float('inf')
    for i in range(3):
        res = max(res, A[-n + i] + sub_max(n - i - 2, m - 1))
    memo[(n, m)] = res
    return res

print((sub_max(N, N//2)))

# Optimized solution
import math
import sys
sys.setrecursionlimit(1000000)

N = int(eval(input()))
A = [int(i) for i in input().split()]

memo = {}
def sub_max(n, m):
    if((n, m) in memo):
        return memo[(n, m)]
    
    if(m == 1 and n >= 1):
        memo[(n, m)] = max(A[-n:])
        return memo[(n, m)]

    if(m > math.ceil(n/2)):
        memo[(n, m)] = -float('inf')
        return -float('inf')
    
    res = -float('inf')
    for i in range(3):
        res = max(res, A[-n + i] + sub_max(n - i - 2, m - 1))
    memo[(n, m)] = res
    return res

print((sub_max(N, N//2)))
# print(memo)
# Original solution
import bisect
import sys
import math
import itertools
sys.setrecursionlimit(10000)

INF = float('inf')

# input macro
def i():
    return int(input())
def ii():
    return list(map(int,input().split(" ")))
def s():
    return input()
def ss():
    return input().split(" ")
def slist():
    return list(input())
#

def join(s):
    return ''.join(s)

#iterate macro
def piter(n,m):
    return itertools.permutations(n,m)
def citer(n,m):
    return itertools.combinations(n,m)

#modulo macro
def modc(a,b,m):
    c = 1
    for i in range(b):
        c = c * (a - i) % m
        c = c * modinv(i + 1,m) % m
    return c
 
def gcd(a, b):
    (x, lastx) = (0, 1)
    (y, lasty) = (1, 0)
    while b != 0:
        q = a // b
        (a, b) = (b, a % b)
        (x, lastx) = (lastx - q * x, x)
        (y, lasty) = (lasty - q * y, y)
    return (lastx, lasty, a)
 
def modinv(a, m):
    (inv, q, gcd_val) = gcd(a, m)
    return inv % m

#bisect macro
def index(a, x):
    #Locate the leftmost value exactly equal to x
    i = bisect_left(a, x)
    if i != len(a) and a[i] == x:
        return i
    return -1

#memoize macro
def memoize(f):
    cache = {}
    def helper(*args):
        if args not in cache:
            cache[(args)] = f(*args)
        return cache[args]
    return helper

@memoize
def nck(a,b,m):
    b = min([a-b,b])
    if (b>a or b<0 or a<0):
        return 0
    elif a == 0:
        return 1
    return (nck(a-1,b-1,m)+nck(a-1,b,m)) % m

nh=list(zip([1,0,-1,0],[0,1,0,-1]))

###########

n=i()
x=ii()
l=i()
q=i()
a,b=[0]*q,[0]*q
for j in range(q):
    a[j],b[j]=ii()

left=[0]*n
right=[0]*n

for (j,hotel) in enumerate(x):
    right[j]=bisect.bisect_right(x,hotel+l)-1
    left[j]=bisect.bisect_left(x,hotel-l)

for j in range(q):
    if a[j]<b[j]:
        cur=a[j]-1
        cnt=0
        while cur<b[j]-1:
            if x[cur]+l>=x[b[j]-1]:
                cnt+=1
                cur=b[j]-1
            else:
                cnt+=1
                cur=right[cur]
        print(cnt)
    else:
        cur=a[j]-1
        cnt=0
        while cur>b[j]-1:
            if x[cur]-l<=x[b[j]-1]:
                cnt+=1
                cur=b[j]-1
            else:
                cnt+=1
                cur=left[cur]
        print(cnt)
            
            
    


# Optimized solution
import bisect
import sys
import math
import itertools
sys.setrecursionlimit(10000)

INF = float('inf')

# input macro
def i():
    return int(input())
def ii():
    return list(map(int,input().split(" ")))
def s():
    return input()
def ss():
    return input().split(" ")
def slist():
    return list(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(list(range(32))):
        if table[k][cur]<b[j]:
            day+=2**k
            cur=table[k][cur]
    print(day+1)
# Original solution
from bisect import bisect_left, bisect_right
import math
import sys
input = sys.stdin.readline


def main():
    N = int(eval(input()))
    X = list(map(int, input().split()))
    L = int(eval(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(eval(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]:
                while dpr[k][a] <= b:
                    a = dpr[k][a]
                    ans += 2**k
            if a < b:
                ans += 1
        else:
            # a > b
            for k in range(ln+1)[::-1]:
                while dpl[k][a] >= b:
                    a = dpl[k][a]
                    ans += 2**k
            if a > b:
                ans += 1
        print(ans)


if __name__ == "__main__":
    main()


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


def main():
    N = int(eval(input()))
    X = list(map(int, input().split()))
    L = int(eval(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(eval(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
            if a < b:
                ans += 1
        else:
            # a > b
            for k in range(ln+1)[::-1]:
                if dpl[k][a] > b:
                    a = dpl[k][a]
                    ans += 2**k
            if a > b:
                ans += 1
        print(ans)


if __name__ == "__main__":
    main()
# Original solution
from bisect import bisect, bisect_left

n = int(eval(input()))
x = list(map(int, input().split()))
l = int(eval(input()))

def search_1(start):
	return bisect(x, x[start] + l) - 1

route = [[] for _ in range(n)]

i = 0 # 親の位置
for i in range(n - 1):
	if route[i] == []:
		j = search_1(i) # カーソルの位置
		num = 1 # 何日目の場所か
		route[i].append(j)
		if route[j] == []:
			route[j] = (i, num)
		else: # 既に他の親が通っている
			route[i] += route[route[j][0]][route[j][1]:]
			continue
		while j < n - 1:
			j = search_1(j)
			num += 1
			route[i].append(j)
			if route[j] == []:
				route[j] = (i, num)
			else: # 既に他の親が通っている
				route[i] += route[route[j][0]][route[j][1]:]
				break
	else:
		continue

# print(route)

def search_2(start, goal):
	if type(route[start]) == type([]):
		return bisect_left(route[start], goal) + 1
	else:
		return bisect_left(route[route[start][0]][route[start][1]:], goal) + 1



q = int(eval(input()))
for _ in range(q):
	a, b = list(map(int, input().split()))
	if a > b:
		a, b = b, a
	print((search_2(a - 1, b - 1)))


# Optimized solution
from bisect import bisect

n = int(eval(input()))
x = list(map(int, input().split()))
l = int(eval(input()))
q = int(eval(input()))

#r[i][j]: jから(2**i)日で行ける右端
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 = list(map(int, input().split()))
	print((search(min(a, b)-1, max(a, b)-1)))