Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

n = int(input())
a = [0]
a += list(map(int,input().split()))
w = [[0]*(n+1) for _ in range(n+1)]

for i in range(n+1):
    for j in range(n+1):
        w[i][j] += abs(a[i] - a[j])

for i in range(1,n+1):
    yen = 0
    p = list(range(n+1)) + [0]
    p.pop(i)

    for j in range(n):
        yen += w[p[j]][p[j+1]]
    print(yen)

### FIXED CODE ###

n = int(input())
a = [0] + list(map(int,input().split())) + [0]
sa = [abs(a[i]-a[i+1]) for i in range(n+1)]
sum_sa = sum(sa)

for i in range(n):
    yen = sum_sa + abs(a[i+2]-a[i]) - sa[i] - sa[i+1]
    print(yen)
### BUGGY CODE ###

n, k, q = map(int, input().split())
a = [ int(input()) for i in range(q) ]

for i in range(1,n+1):
    x = a.count(i)
    if k-q+x > 0:
        print('Yes')
    else:
        print('No')

### FIXED CODE ###

n, k, q = map(int, input().split())
a = [ int(input()) for i in range(q) ]
score = [k-q]*n
for i in a:
    score[i-1] += 1
for i in score:
    print('Yes' if i > 0 else 'No')
### BUGGY CODE ###

n = int(input())

def divisior(n):
    a = []
    i = 1
    while (i*i <= n):
        if n%i == 0:
            a.append(i)
            if (i*i == n): continue
            a.append(n//i)
        i += 1

    return a

ans = 0
a = divisior(n)

for x in a:
    if x == 1: continue
    tmp = n
    while (tmp%x == 0): tmp = tmp//x
    if (tmp%x == 1) : ans += 1

b = divisior(n-1)

ans = ans + len(b) -1

print(ans)




### FIXED CODE ###

n = int(input())

def divisior(n):
    a = []
    i = 1
    while (i*i <= n):
        if n%i == 0:
            a.append(i)
            if (i*i != n): a.append(n//i)
        i += 1
    return a

ans = 0
a = divisior(n)

for x in a[1:]:
    tmp = n
    while (tmp%x == 0): tmp = tmp//x
    if (tmp%x == 1) : ans += 1

b = divisior(n-1)

ans = ans + len(b) -1

print(ans)
### BUGGY CODE ###

n,m=map(int,input().split())
data=sorted([tuple(map(int,input().split())) for i in range(n)])
ans=0
while True:
  if m == 0:
    print(ans)
    exit()
  elif data[0][1]<=m:
    ans+=data[0][0]*data[0][1]
    m-=data[0][1]
    data=data[1:]
  else:
    ans+=data[0][0]*m
    m=0

### FIXED CODE ###

n,m=map(int,input().split())
dataset=sorted([tuple(map(int,input().split())) for i in range(n)])
ans=0
for data in dataset:
  if m==0:
    print(ans)
    exit()
  tmp=min(data[1],m)
  ans+=tmp*data[0]
  m-=tmp
print(ans)
### BUGGY CODE ###

from bisect import bisect_left

N, M = map(int, input().split())
AB = [[int(i) for i in input().split()] for _ in range(N)]

AB.sort(key=lambda x: x[1], reverse=True)

s = [i for i in range(1, M + 1)]
ret = 0
for a, b in AB :
    if not s :
        break
    if a > s[-1] :
        continue
    
    a = bisect_left(s, a)
    s.pop(a)
    ret += b
print(ret)

### FIXED CODE ###

from heapq import heappush, heappop

N, M = map(int, input().split())
AB = [[] for _ in range(M+1)]

for _ in range(N) :
    a, b = map(int, input().split())
    if a <= M :
        AB[M-a].append(b)
    
q = []
for a in range(M+1) :
    for b in AB[a] :
        heappush(q, b)
        if len(q) > a + 1 :
            heappop(q)
            
print(sum(q))
### BUGGY CODE ###

N = int(input())

S = []

for i in range(N):
  S.append(input())

set_S = list(set(S))
ans = []
max_cnt = 0
for i in range(len(set_S)):
  cnt = 0
  for j in range(N):
    if set_S[i] == S[j]:
      cnt += 1
  if max_cnt <= cnt:
    max_cnt = cnt
    temp = [set_S[i],cnt]
    ans.append(temp)

ans_f = []

for i in range(len(ans)):
  if ans[i][1] == max_cnt:
    ans_f.append(ans[i][0])

ans_f.sort()

for i in range(len(ans_f)):
  print(ans_f[i])

### FIXED CODE ###

N = int(input())

d = {}

for _ in range(N):
  S = input()
  if S in d:
    d[S] += 1
  else:
    d[S] = 1

m = max(d.values())

for s in sorted(k for k in d if d[k] == m):
  print(s)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

n, m = [int(x) for x in input().split()]
ab = [tuple(int(x) for x in input().split()) for _ in range(m)]

ab = [may for may in ab if may[0] == 1 or may[1] == n]
ab.sort()
ab_end_n = [may for may in ab if may[1] == n]

for m in ab:
    if m[0] == 1: 
        for i in ab_end_n:
            if m[1] == i[0]: print('POSSIBLE'); exit()
        continue
    else:
        break
print('IMPOSSIBLE')

### FIXED CODE ###

n, m, *ab = map(int, open(0).read().split())
from_1, to_n = set(), set()
for a, b in zip(*[iter(ab)] *2):
    if a == 1: from_1.add(b)
    if b == n: to_n.add(a)
print('POSSIBLE' if from_1 & to_n else "IMPOSSIBLE")
### BUGGY CODE ###

MOD = 10**9 + 7

s = input()
n = len(s)

dp = [[0]* 13 for i in range(n+1)]
dp[0][0] = 1

for i in range(n):
    if s[i] != '?':
        for j in range(13):
            a = s[i]
            a = int(a)
            keta = (j*10 + a) % 13
            dp[i+1][keta] += dp[i][j]
            dp[i+1][keta] % MOD
    else:
        for j in range(13):
            for k in range(10):
                keta = (j*10 + k) % 13
                dp[i+1][keta] += dp[i][j]
                dp[i+1][keta] % MOD
                
print(dp[n][5] % MOD)

### FIXED CODE ###

MOD = 10**9 + 7

s = input()
n = len(s)

dp = [[0]* 13 for i in range(n+1)]
dp[0][0] = 1

for i in range(n):
    if s[i] != '?':
        for j in range(13):
            a = s[i]
            a = int(a)
            keta = (j*10 + a) % 13
            dp[i+1][keta] += dp[i][j]
            dp[i+1][keta] %= MOD
    else:
        for j in range(13):
            for k in range(10):
                keta = (j*10 + k) % 13
                dp[i+1][keta] += dp[i][j]
                dp[i+1][keta] %= MOD
                
print(dp[n][5] % MOD)
### BUGGY CODE ###

from collections import deque
from collections import defaultdict

N, Q = list(map(int, input().split()))
AB = []
PX = []
for _ in range(N-1):
    AB.append(list(map(int, input().split())))
for _ in range(Q):
    PX.append(list(map(int, input().split())))
PX.sort()

q = deque()
ans = [0] * (N+1)

T = defaultdict(list)
for ab in AB:
    a, b = ab
    T[a].append(b)

P = defaultdict(int)
for px in PX:
    p, x = px
    P[p] += x
ans[1] = P[1]

for t in T[1]:
    q.append([1, t])
while q:
    a, b = q.popleft()
    ans[b] += ans[a] + P[b]
    for t in T[b]:
        q.append([b, t])

print(*ans[1:])


### FIXED CODE ###

from collections import deque
from collections import defaultdict
import sys
readline = sys.stdin.readline

N, Q = list(map(int, readline().split()))
T = defaultdict(list)
for _ in range(N-1):
    a, b = list(map(int, readline().split()))
    T[a].append(b)

P = defaultdict(int)
for _ in range(Q):
    p, x = list(map(int, readline().split()))
    P[p] += x

q = deque()
ans = [0] * (N+1)
ans[1] = P[1]

for t in T[1]:
    q.append([1, t])
while q:
    a, b = q.popleft()
    ans[b] += ans[a] + P[b]
    for c in T[b]:
        q.append([b, c])

print(*ans[1:])
### BUGGY CODE ###

n = int(input())
LA = [int(input()) for i in range(n)]
LB = []
LB.extend(LA)
for i in range(n):
    del LB[i]
    print(max(LB))
    LB = []
    LB.extend(LA)

### FIXED CODE ###

n = int(input())
LA = [int(input()) for i in range(n)]
LB = []
LB.extend(LA)
LA.sort()
z = LA[-1]
y = LA[-2]
for i in range(n):
    if LB[i] == z:
        print(y)
    else:
        print(z)
### BUGGY CODE ###

import numpy as np

def factorial(i):
    ans = 1
    for j in range(1,i+1):
        ans *= j
    return ans
N = int(input())
A = [input() for i in range(N)]
a = []
for i in A:
    b = list(i)
    b.sort()
    a.append(b)

a.sort()
c = list(map(list, set(map(tuple, a))))
d=[]
for i in c:
    d.append(a.count(i))
count=0
for i in d:
    if i ==1:
        continue
    if i>2:
        count += factorial(i) // (factorial(i - 2) * factorial(2))
    elif i ==2:
        count += 1
print(count)

### FIXED CODE ###

N = int(input())
A=[]
S={}
for i in range(N):
    a = list(input())
    a.sort()
    b = ''.join(a)
    if b not in S:
        S[b] = 1
    else:
        S[b] += 1


count=0
for i in S.values():
    if i==1:
        continue
    count += i*(i-1)//2
print(count)
### BUGGY CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy,copy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

def main():
    n = INT()
    a = LIST()
    ans = [a.index(i)+1 for i in range(1, n+1)]

    print(*ans)

if  __name__=='__main__':
    main()


### FIXED CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy,copy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

def main():
    n = INT()
    a = LIST()
    l = [[a[i], i+1] for i in range(n)]
    l.sort()
    ans = [x[1] for x in l]
    print(*ans)

if  __name__=='__main__':
    main()
### BUGGY CODE ###

n, q = [int(i) for i in input().split() ]
s = input() #文字列
lr = list([])
for i in range(q):
    lr.append([int(i) for i in input().split() ])

ll = list([])
for i, c in enumerate(s):
    if((c == "A") and (i+1 <n) and (s[i+1] =="C")):
        ll.append(i+1)

for i in range(q):
    ans = 0
    for m in ll:
        if (m >= lr[i][0]) and (m+1 <=lr[i][1]):
            ans += 1
        elif m >= lr[i][1]:
            break
    print(ans)

### FIXED CODE ###

n, q = [int(i) for i in input().split() ]
s = input() #文字列
lr = list([])
count = [0 for i in range(n)]
for i in range(q):
    lr.append([int(i) for i in input().split() ])

ll = list([])
now = 0
for i, c in enumerate(s):
    if((c == "C") and (i>0) and (s[i-1] =="A")):
        now += 1
    count[i] = now

for i in range(q):
    ans = 0
    print(count[lr[i][1]-1] - count[lr[i][0]-1])
### BUGGY CODE ###

N=int(input())
a=[0]*(N-1)
b=[0]*(N-1)
c=[0]*(N-1)
d=[[] for _ in range(N)]
e=[ set() for _ in range(N)] #存在する色のリスト
maxi=0
for i in range(N-1):
    a[i],b[i] = map(int,input().split())
    d[a[i]-1].append(b[i]-1)
    d[b[i]-1].append(a[i]-1)
for j in d:
    maxi=max(maxi,len(j))
for i in range(N-1):
    col=1
    while col in e[a[i]-1] or col in e[b[i]-1]:
        col +=1
        if col==maxi+1:
            col=1
    c[i]=col
    e[a[i]-1].add(col)
    e[b[i]-1].add(col)
   
print(maxi)
for color in c:
    print(color)


### FIXED CODE ###

from collections import deque

N=int(input())
a=[0]*(N-1)
b=[0]*(N-1)
c=[set() for _ in range(N)] # 使用している色
d=[set() for _ in range(N)] # 隣接リスト
e=[ False for _ in range(N)] #訪問ずみかどうか
f=[0]*N  #答え
for i in range(N-1):
    a[i],b[i] = map(int,input().split())
    d[a[i]-1].add(b[i]-1)
    d[b[i]-1].add(a[i]-1)

maxi=max([len(d[i]) for i in range(N-1)])
print(maxi)
#print("c:",c)
#print("d",d)
#print("e",e)

#x=0としてBFSする

v=deque([0])
e[0]=True
color=1

while v:
  p = v.popleft()
  for q in d[p]:
    if e[q]==False:
      while color in c[p]:
        color +=1
        if color>maxi:
          color=1
      c[p].add(color)
      c[q].add(color)
      f[q]=color
      e[q]=True
      v.append(q)
      
for i in range(N-1):
  print( f[b[i]-1])
### BUGGY CODE ###

s=input()
a=[0]*(len(s)+1)
for i in range(len(a)):
  j=i
  r=0
  l=0
  while j < len(s) and s[j] == '>':
    r+=1
    j+=1
  j=i
  while 0 < j and s[j-1] == '<':
    l+=1
    j-=1   
  a[i]=max(l,r)
print(sum(a))

### FIXED CODE ###

s=input()
a=[0]*(len(s)+1)
r=0
l=0
for i in range(len(a)):
  j=i
  if r==0:
    while j < len(s) and s[j] == '>':
      r+=1
      j+=1
  else:
    r-=1
  if i !=0 and s[i-1] == '<':
    l+=1
  else:
    l=0
  a[i]=max(l,r)
print(sum(a))
### BUGGY CODE ###

#!usr/bin/env python3
from collections import defaultdict
from heapq import heappush, heappop
import sys
import math
import bisect
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return list(sys.stdin.readline())
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)]
mod = 1000000007
 
#A
"""
a, b = LI()
print((a+b+1)//2)
"""
 
#B
"""
a = S()
a = a[:-1]
b = S()
b = b[:-1]
a.sort()
b.sort(reverse=True)
if a < b:
    print("Yes")
else:
    print("No")
"""
 
#C
n = I()
a = LI()
seta = set(a)
ans = 0
for i in seta:
    x = a.count(i)
    if x != 0 and x >= i:
        ans += x - i
    else:
        ans += x
print(ans)

### FIXED CODE ###

#!usr/bin/env python3
from collections import defaultdict
from heapq import heappush, heappop
import sys
import math
import bisect
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return list(sys.stdin.readline())
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)]
mod = 1000000007

#A
"""
a, b = LI()
print((a+b+1)//2)
"""

#B
"""
a = S()
a = a[:-1]
b = S()
b = b[:-1]
a.sort()
b.sort(reverse=True)
if a < b:
    print("Yes")
else:
    print("No")
"""

#C
n = I()
a = LI()
a.sort()
seta = set(a)
ans = 0
for i in seta:
    x = bisect.bisect_right(a,i) - bisect.bisect_left(a,i)
    if x != 0 and x >= i:
        ans += x - i
    else:
        ans += x
print(ans)
### BUGGY CODE ###

import copy
N = int(input())
A = [list(map(int, input().split())) for i in range(N)]
B = copy.deepcopy(A)
for i in range(N):
    for j in range(N):
        if i == j:
            continue
        for k in range(N):
            if k == i or k == j:
                continue
            else:
                B[i][k] = min(B[i][k], B[i][j]+B[j][k])

if A == B:
    ans = 0
    for i in range(N):
        ans += sum(A[i])
        for j in range(N):
            if i == j:
                continue
            for k in range(N):
                if k == i or k == j:
                    continue
                else:
                    if A[i][k] == A[i][j]+A[j][k]:
                        ans -= B[i][k]
    print(ans//2)
else:
    print(-1)


### FIXED CODE ###

import copy
N = int(input())
A = [list(map(int, input().split())) for i in range(N)]
B = copy.deepcopy(A)
table = [[True]*N for i in range(N)]
ans = 0
for i in range(N):
    for j in range(N):
        if i == j:
            continue
        for k in range(N):
            if k == i or k == j:
                continue
            else:
                if B[i][k] == B[i][j]+B[j][k]:
                    table[i][k] = False
                B[i][k] = min(B[i][k], B[i][j]+B[j][k])


if A == B:
    for i in range(N):
        for j in range(N):
            if table[i][j]:
                ans += B[i][j]
    print(ans//2)
else:
    print(-1)
### BUGGY CODE ###

def f():
    import sys
    input=sys.stdin.readline
    n=int(input())
    a=[int(j) for j in input().split()]
    import numpy as np
    dp=np.zeros((n,n,2),dtype=np.int64)

    for i in range(1,1+n):
        for j in range(n-i+1):
            #j~j+i-1
            if i==1:
                dp[j][j][1]=a[j]
                continue
            tmp=10**18
            for k in range(i-1):
                #j~j+k,j+k+1~j+i-1
                if dp[j][j+k].sum()+dp[j+k+1][j+i-1].sum()<tmp:
                    tmp=dp[j][j+k].sum()+dp[j+k+1][j+i-1].sum()
                    dp[j][j+i-1][0]=tmp
                    dp[j][j+i-1][1]=dp[j][j+k][1]+dp[j+k+1][j+i-1][1]
    print(dp[0][n-1][0])

f()

### FIXED CODE ###

def f():
    import sys
    import numpy as np
    input=sys.stdin.readline
    n=int(input())
    a=np.array([0]+[int(j) for j in input().split()])
    np.cumsum(a,out=a)
    dp=np.zeros((n,n+1),np.int64)

    for i in range(1,n):
        l=np.arange(n-i)
        r=np.arange(i+1,n+1)
        m=(np.arange(1,i+1)+l[:,np.newaxis]).T
        dp[l,r]=np.amin(dp[l,m]+dp[m,r],0)+a[r]-a[l]
    print(dp[0][n])
f()
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
import itertools


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    # Failed to predict input format
    N, M, X = [int(x) for x in input().split()]
    C = []
    A = []
    for i in range(N):
        tmp = [int(x) for x in input().split()]
        C.append(tmp[0])
        A.append(tmp[1:])
    CA = [[C[i], v] for i, v in enumerate(A)]
    l = list(itertools.permutations(CA, N))
    anss = [100100100] * len(l)
    for i, v in enumerate(l):
        arr = [0] * M
        s = 0
        for j in v:
            arr = python_list_add(arr, j[1])
            s += j[0]
            if all([x >= X for x in arr]):
                anss[i] = s
                break
    ans = min(anss)
    if ans == 100100100:
        print(-1)
        return
    print(ans)
    return


def python_list_add(in1, in2):
    return [a + b for a, b in zip(in1, in2)]


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
import itertools


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    N, M, X = [int(x) for x in input().split()]
    C = []
    A = []
    for i in range(N):
        tmp = [int(x) for x in input().split()]
        C.append(tmp[0])
        A.append(tmp[1:])
    CA = [[C[i], v] for i, v in enumerate(A)]

    # TLE
    # l = list(itertools.permutations(CA, N))
    # anss = [100100100] * len(l)
    # for i, v in enumerate(l):
    #     arr = [0] * M
    #     s = 0
    #     for j in v:
    #         arr = python_list_add(arr, j[1])
    #         s += j[0]
    #         if all([x >= X for x in arr]):
    #             anss[i] = s
    #             break
    # ans = min(anss)
    # if ans == 100100100:
    #     print(-1)
    #     return
    # print(ans)

    # bit全探索
    anss = []
    for i in range(2 ** N):
        s = 0
        arr = [0] * M
        for j in range(N):
            if i >> j & 1:
                s += CA[j][0]
                arr = python_list_add(arr, CA[j][1])
            if all([x >= X for x in arr]):
                anss.append(s)
    print(min(anss) if anss else -1)

    return


def python_list_add(in1, in2):
    return [a + b for a, b in zip(in1, in2)]


if __name__ == '__main__':
    main()
### BUGGY CODE ###

H, W, K = map(int, input().split())
S = []
inf = 100000
ans = inf
for _ in range(H):
    S.append([int(x) for x in input()])
for i in range(2**(H-1)):
    hlis = [0]
    for j in range(H-1):
        if ((i>>j) & 1):
            hlis.append(j+1)
    hlis.append(H)
    wkireme = 0
    numwkireme = 0
    Flag1 = True
    Flag2 = True
    w = 1
    while Flag1:
        for n in range(len(hlis)-1):
            s = 0
            for num in range(hlis[n],hlis[n+1]):
                s += sum(S[num][wkireme:wkireme+w])
            if s > K:
                if w == 1:
                    Flag2 = False
                    Flag1 = False
                    break
                else:
                    wkireme = wkireme + w -1
                    numwkireme += 1
                    w = 1
                    break
        else:
            if wkireme + w >= W:
                Flag1 = False
            else:
                w += 1
    if Flag2:
        ans = min(ans, numwkireme + len(hlis) -2)
print(ans)


### FIXED CODE ###

def main():
    import sys
    inf = 100100100
    ans = inf
    H, W, K = map(int, input().split())
    S = [0]*H
    for i in range(H):
        S[i] = [int(x) for x in sys.stdin.readline().strip()]
    for i in range(2**(H-1)):
        group = [0]
        g = 0
        for j in range(H-1):
            if (i >> j) & 1:
                g += 1
            group.append(g)
        g += 1
        c = [[0 for _ in range(W)] for __ in range(g)]
        for j in range(H):
            for k in range(W):
                c[group[j]][k] += S[j][k]
        num = g-1
        now = [0]*g
        def large(now):
            for n in now:
                if n > K:
                    return True
            else:
                return False
        def v_vec(twodlis, k):
            ans = []
            for lis in twodlis:
                ans.append(lis[k])
            return ans
        for k in range(W):
            for n in range(len(now)):
                now[n] = now[n] + v_vec(c,k)[n]
            if large(now):
                now = v_vec(c,k)
                num += 1
                if large(now):
                    num = inf
                    break

        ans = min(ans, num)
    print(ans)

if __name__ == "__main__":
    main()
### BUGGY CODE ###

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)


### FIXED CODE ###

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)