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

N = int(input())
A = sorted([int(i) for i in input().split()])
B = sorted([int(i) for i in input().split()])
C = sorted([int(i) for i in input().split()])

count = 0

for i in range(N):
    for j in range(N):
        if A[i] < B[j]:
            for k in range(N):
                if B[j] < C[k]:
                    count += 1

print(count)

### FIXED CODE ###

from bisect import bisect_right, bisect_left
N = int(input())
A = sorted([int(i) for i in input().split()])
B = sorted([int(i) for i in input().split()])
C = sorted([int(i) for i in input().split()])

count = 0

for b in B:
    i = bisect_left(A, b)
    k = bisect_right(C, b)
    count += i * (N-k)

print(count)
### BUGGY CODE ###

N = int(input())
print( sum(range(1,N)))

### FIXED CODE ###

N = int(input())
print( int( (N * (N -1) )//2))
### BUGGY CODE ###

N = int(input())
S = input()

p = 10**6

for i in range(N):
    Sl = S[:i] if i > 0 else "0"
    Sr = S[i+1:] if i < N-1 else "0"
    if p > Sl.count("W") + Sr.count("E"):
        p = Sl.count("W") + Sr.count("E")

print(p)


### FIXED CODE ###

N = int(input())
S = input()

listw = [0]
for i in range(N):
    listw.append(listw[-1]+1 if S[i] == "W" else listw[-1])

liste = [0]
for i in range(N):
    liste.append(liste[-1]+1 if S[i] == "E" else liste[-1])

list = [0]*N
for i in range(N):
    list[i] = listw[i] + liste[-1] - liste[i+1 if i != N-1 else -1]

list.sort()

print(list[0])
### BUGGY CODE ###

N, P = map(int, input().split())
S = list(input())

a = [0] * (N + 1)
r = [0] * P

if P != 2 and P != 5:
    tenfactor=1
    for i in range(1,N+1):
        a[i] = (int(S[N-i])*tenfactor+a[i-1])
        tenfactor*=10
        r[a[i] % P] += 1
    r[0] += 1
    ans = 0
    for i in range(P):
        ans += r[i] * (r[i] - 1) // 2
elif P == 2:
    ans = 0
    for i in range(N):
        if int(S[i]) % 2 == 0:
            ans += i + 1
elif P == 5:
    ans = 0
    for i in range(N):
        if int(S[i]) == 0 or int(S[i]) == 5:
            ans += i + 1

print(ans)



### FIXED CODE ###

N, P = map(int, input().split())
S = input()

a = [0] * (N + 1)

if P != 2 and P != 5:
    tenfactor=1
    for i in range(1,N+1):
        a[i] = ((int(S[N-i])*tenfactor+a[i-1])%P)
        tenfactor*=10
        tenfactor%=P

    ans = 0
    from collections import Counter
    C=Counter(a)
    for v,i in C.items():
        ans += (i * (i - 1) // 2)
elif P == 2:
    ans = 0
    for i in range(N):
        if int(S[i]) % 2 == 0:
            ans += i + 1
elif P == 5:
    ans = 0
    for i in range(N):
        if int(S[i]) == 0 or int(S[i]) == 5:
            ans += i + 1

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

from itertools import *
from math import *

D, G = map(int, input().split())
probs = [list(map(int, input().split())) for _ in range(D)]
seq = list(range(D))
x = list(permutations(seq, D))
#print(x)
ans = float("inf")
G2=G
for i in range(len(x)):
    cand = x[i]
    cnt = 0
    G=G2
    for j in range(D):
        ind = cand[j]
        probpoint = (ind + 1) * 100
        if G<=0:
            break
        if G <= probpoint * (probs[ind][0] - 1):
            cnt = cnt + ceil(G / probpoint)
            G=G-probpoint*ceil(G / probpoint)
        else:
            cnt=cnt+probs[ind][0]
            G=G-(probpoint * probs[ind][0]+probs[ind][1])
    ans=min(ans,cnt)
print(ans)




### FIXED CODE ###

import sys
from itertools import *
from math import *
input=sys.stdin.readline
D, G = map(int, input().split())
probs = [list(map(int, input().split())) for _ in range(D)]
G2 = G
seq = tuple(range(D))
x=[]
for i in range(0,D+1):
    l=combinations(seq,i)
    for j in l:
        x.append(j)
x=tuple(x)
#print(x)
infty=100000
#print(x)
ans = infty
for cand in x:
    cnt = 0
    G=G2
    l=[0]*D
    for ind in cand:
        probpoint = (ind + 1) * 100
        G=G-(probpoint * probs[ind][0]+probs[ind][1])
        cnt = cnt + probs[ind][0]
        l[ind]=1
    #print(l,G,cnt)
    for i in range(D-1,-1,-1):
        if G<=0:
            break
        elif l[i]==0:
            probpoint = (i + 1) * 100
            num=ceil(G/probpoint)
            if num<probs[i][0]:
                G=G-num*probpoint
                cnt=cnt+num
            #print(cnt)
            break
    if G<=0:
        ans=min(ans,cnt)
print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-

import math

def main():
     x = int(input())
     # x は 正の整数
     # ans = a^5 - b^5 = x となる a, b

     b = 0
     while(True):
          b_x = pow(b, 5)
          a_x = x + b_x
          a = pow(a_x, 1 / 5)

          # print('a:{}, b:{}'.format(a, b))

          if type(a) == float:
               if a.is_integer():
                    print(int(a), b)
                    break

          if b <= 0:
               b -= 1
               b = b * (-1)
          else:
               b = b * (-1)

if __name__ == "__main__":
    main()


### FIXED CODE ###

# -*- coding: utf-8 -*-

import math

def main():
     x = int(input())
     # x は 正の整数
     # ans = a^5 - b^5 = x となる a, b

     num_list = []
     len_num_list = 0

     a = 0
     end = False
     while(not end):
          num_list.append(pow(a, 5))
          len_num_list += 1

          # print(a)
          # print(num_list)

          for i in range(len_num_list):
               for j in range(i, len_num_list):
                    i_5div = num_list[i]
                    j_5div = num_list[j]

                    if i_5div - j_5div == x:
                         print('{} {}'.format(i, j))
                         end = True
                         break
                    if j_5div - i_5div == x:
                         print('{} {}'.format(j, i))
                         end = True
                         break
                    if i_5div + j_5div == x:
                         print('{} {}'.format(i, j * (-1)))
                         end = True
                         break
                    if j_5div + i_5div == x:
                         print('{} {}'.format(j, i * (-1)))
                         end = True
                         break

          a += 1


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

def resolve():
    import sys
    input = sys.stdin.readline
    # 整数 1 つ
    n = int(input())
    # 整数複数個
    # a, b = map(int, input().split())
    # 整数 N 個 (改行区切り)
    # N = [int(input()) for i in range(N)]
    # 整数 N 個 (スペース区切り)
    L = list(map(int, input().split()))
    # 整数 (縦 H 横 W の行列)
    # A = [list(map(int, input().split())) for i in range(H)]

    L = sorted(L, reverse=True)

    cnt = 0
    for i in range(n-2):
        for j in range(i+1, n-1):
            for k in range(j+1, n):
                if L[i]-L[j] < L[k]:
                    cnt += 1
                else:
                    break

    print(cnt)
resolve()

### FIXED CODE ###

def resolve():
    import sys
    input = sys.stdin.readline
    # 整数 1 つ
    n = int(input())
    # 整数複数個
    # a, b = map(int, input().split())
    # 整数 N 個 (改行区切り)
    # N = [int(input()) for i in range(N)]
    # 整数 N 個 (スペース区切り)
    L = list(map(int, input().split()))
    # 整数 (縦 H 横 W の行列)
    # A = [list(map(int, input().split())) for i in range(H)]

    L.sort()
    import bisect

    cnt = 0
    for i in range(n-2):
        for j in range(i+1, n-1):
            k = bisect.bisect_left(L, (L[i]+L[j]))
            if k > j:
                cnt += k - j -1

    print(cnt)


resolve()
### BUGGY CODE ###

n = int(input())
nn = 0

if n >= 357:
    for i in range(357,n+1):
        s = str(i)
        if ('0' in s or '1' in s or '2' in s or '4' in s or '6' in s or '8' in s or '9' in s) is False:
            if '3' in s:
              if '5' in s:
                if '7' in s:
                  #print(i)
                  nn += 1
print(nn)

### FIXED CODE ###

def nextn(n):
    if n == 0:
        return 3
    elif n % 10 == 3:
        return n+2
    elif n % 10== 5:
        return n+2
    elif n % 10 ==7:
        return nextn(n//10)*10 + 3

N = int(input())
n = 357
ans = 0
while n <= N:
    s = str(n)
    a = [False,False,False]
    for c in s:
        if c == '3':
            a[0] = True
        elif c == '5':
            a[1] = True
        elif c == '7':
            a[2] = True
        else:
            print(s)
    if all(a):
        ans += 1
    n = nextn(n) 
print(ans)
### BUGGY CODE ###

n=int(input())
plan=[None]*n
for i in range(n):
  p=list(map(int,input().split()))
  for j in range(len(p)):
    p[j]=p[j]-1
  plan[i]=p

# print(plan)
d=0
error=False
while True:
  d=d+1
#  print(str(d)+" day")
  done=[True]*n
  thisday=False
  for i in range(n):
    if done[i]==False:
      continue
    if len(plan[i])==0:
      continue
    target=plan[i][0]
    if done[target]==False:
      continue
    if len(plan[target])==0:
      continue
#    print("plan[i]")
#    print(plan[i])
#    print("target:"+str(target))
#    print("plan[target]")
#    print(plan[target])
    if plan[target][0]==i:
      # 試合を行う
#      print(str(i)+":"+str(plan[i][0])+" and "+str(target)+":"+str(plan[target][0])+ "fight!")
      plan[i].pop(0)
      plan[target].pop(0)
      done[i]=False
      done[target]=False
#      print("plan[i],plan[target] after that")
#      print(plan[i])
#      print(plan[target])
      thisday=True
  if thisday==False:
    # 試合が一つも組めなかった
    # ぜんぶからになっているなら正常終了　そうでなければ-1
    for i in range(len(plan)):
      if len(plan[i])!=0:
        error=True
    break
  
if error:
  print(-1)
else:
  print(d-1)

### FIXED CODE ###

N=int(input())
a=[[0 for j in range(N-1)] for i in range(N)]
for i in range(N):
  line=list(map(int,input().split()))
  for j in range(N-1):
    a[i][j]=line[j]-1
  a[i]=a[i][::-1]
    
q=[]

#seen=[[False for j in range(N)] for i in range(N)]

# 選手nが試合できるならqueに入れる
def check(i):
  if len(a[i])==0:
    return False
  j=a[i][-1]
  if a[j][-1]==i:
    q.append([i,j])
  
for i in range(N):
  check(i)
  
from collections import defaultdict

day=0
while q:
  day+=1
 # q=sorted(q)
  prevQ=q.copy()
  q=[]
  matched=defaultdict(list)
  for p in prevQ:
    i=p[0]
    j=p[1]
    if i>j:
      i,j=j,i
    if matched[i]:
      continue
    a[i].pop()
    a[j].pop()
    check(i)
    check(j)
    matched[i].append(j)
    
for i in range(N):
  if len(a[i])!=0:
    print(-1)
    break
else:
  print(day)
### BUGGY CODE ###

import sys
def input():
    return sys.stdin.readline()[:-1]
n,k=map(int,input().split())
a=list(map(int,input().split()))
mod=10**9+7

def cmb(n, r, mod):
   if ( r<0 or r>n ):
       return 0
   r = min(r, n-r)
   return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 
N = 10**4
g1 = [1, 1] 
g2 = [1, 1] 
inverse = [0, 1] 

for i in range( 2, N + 1 ):
   g1.append( ( g1[-1] * i ) % mod )
   inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
   g2.append( (g2[-1] * inverse[-1]) % mod )

# a = cmb(n,r,mod)

a.sort()
ans=0
if n==1 or k==1:
    print(0)
    exit()
# c=cmb(n-1,k-1,mod)
tmp=max(a)-min(a)
suuji=[[0,0] for i in range(tmp+1)]
low=min(a)
# for i in range(n):
#     print(a[i]-low)
#     suuji[a[i]-low][0]+=i
#     suuji[a[i]-low][1]+=c-i
for i in range(len(a)):
    ans+=a[i]*cmb(i,k-1,mod)
    ans-=a[i]*cmb(n-i-1,k-1,mod)
    ans%=mod
# print(suuji)
print(ans)

### FIXED CODE ###

import sys
def input():
    return sys.stdin.readline()[:-1]
n,k=map(int,input().split())
a=list(map(int,input().split()))
mod=10**9+7

class Combination:
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)
 
    def __call__(self, n, r):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod
 
    def make_factorial_list(self, n):
 
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv
 
    def make_modinv_list(self, n):
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv

a.sort()
ans=0
if n==1 or k==1:
    print(0)
    exit()
# c=cmb(n-1,k-1,mod)
comb = Combination(10**5)
# for i in range(n):
#     print(a[i]-low)
#     suuji[a[i]-low][0]+=i
#     suuji[a[i]-low][1]+=c-i

for i in range(len(a)):
    if i>=k-1:
        ans+=a[i]*comb(i,k-1)
        ans%=mod
    if n-i-1>=k-1:
        ans-=a[i]*comb(n-i-1,k-1)
        ans%=mod
    ans%=mod
# print(suuji)
print(ans)
### BUGGY CODE ###

N,K=map(int,input().split())
S=[]
NUM=998244353
for _ in range(K):
    l,r=map(int,input().split())
    for i in range(l,r+1):
        S.append(i)
S.sort()
dp=[0]*(N+1)
dp[1]=1
for i in range(2,N+1):
    for s in S:
        if i-s<=0: break
        dp[i]+=dp[i-s]
        dp[i]%=NUM

print(dp[N])


### FIXED CODE ###

N,K=map(int,input().split())
S=[list(map(int,input().split())) for _ in range(K)]

NUM=998244353
dp=[0]*(N+1)
dp[1]=1
sums=[0]*(N+1)
sums[1]=1
for i in range(2,N+1):
    for s in S:
        _l,_r=i-s[0],i-s[1]-1
        if _l<0:
            continue
        elif _r<0:
            _r=0
        dp[i]+=sums[_l]-sums[_r]
        dp[i]%=NUM
    sums[i]=dp[i]+sums[i-1]
    sums[i]%=NUM

print(dp[N])
### BUGGY CODE ###

n = int(input())
A = list(map(int, input().split()))

setA = set(A)
an = 0
for num in setA:
    d = A.count(num)
    an += d*(d-1)//2

for i in range(n):
    ans = an
    t = A[i]
    e = A.count(A[i])
    ans -= e*(e-1)//2
    ans += (e-1)*(e-2)//2
    print(ans)

### FIXED CODE ###

N=int(input())
K=list(map(int, input().split()))
from collections import Counter
ans = 0
C = Counter(K)
for k, v in C.items():
    ans += v*(v-1)//2

for a in K:
    e = C[a]
    print(ans-e*(e-1)//2+(e-1)*(e-2)//2)
### BUGGY CODE ###

from collections import Counter
import math

N = int(input())
Al = list(map(int, input().split()))
d_di = {}
d_in = {}

counter = Counter(Al)

As_l = list(set(Al))

for n in As_l:
    cnt = int(counter[n])
    if cnt > 1:
        d_di[n] = (math.factorial(cnt) // (2 * math.factorial(cnt - 2)))
    else:
        pass
    if cnt > 2:
        d_in[n] = (math.factorial(cnt-1) // (2 * math.factorial(cnt - 3)))
    else:
        d_in[n] = 1
# print(d_di)
# print(d_in)
total = sum(v for v in d_di.values())
for k in Al:
    ans = total - (counter[k]-1)
    if ans < 0:
        ans = 0
    else:
        pass
    print(ans)


### FIXED CODE ###

from collections import Counter
import math

N = int(input())
Al = list(map(int, input().split()))
d_di = {}
#d_in = {}
counter = Counter(Al)
As_l = list(set(Al))
for n in As_l:
    cnt = int(counter[n])
    if cnt > 1:
        d_di[n] = (math.factorial(cnt) // (2 * math.factorial(cnt - 2)))
    else:
        pass
#    if cnt > 2:
#        d_in[n] = (math.factorial(cnt-1) // (2 * math.factorial(cnt - 3)))
#    else:
#        d_in[n] = 1
# print(d_di)
# print(d_in)
total = sum(v for v in d_di.values())
for k in Al:
    ans = total - (counter[k]-1)
    if ans < 0:
        ans = 0
    else:
        pass
    print(ans)
### BUGGY CODE ###

N,C = map(int,input().split())
X = [0]*N
V = [0]*N
XX = [0]*N
VV = [0]*N
for i in range(N):
    X[i],V[i] = map(int,input().split())
    XX[N-i-1] = C-X[i]
    VV[N-i-1] = V[i]
from numpy import array as arr
V = arr(V)
VV = arr(VV)
a = [0]*(2*N-1)
b = [0]*(2*N-1)
for i in range(N):
    x = X[i]
    v = V[:i+1].sum()
    xx = XX[i]
    vv = VV[:i+1].sum()
    a[i] = v-x
    b[i] = vv-xx
aa = arr([0]*N)
bb = arr([0]*N)
for i in range(N):
    aa[i] = max(a[:i+1])
    bb[i] = max(b[:i+1])
for i in range(N-1):
    x = 2*(C-X[-i-1])
    v = V[-i-1:].sum()
    xx = 2*(C-XX[-i-1])
    vv = VV[-i-1:].sum()
    a[N+i] = v-x+aa[N-i-2]
    b[N+i] = vv-xx+bb[N-i-2]
a.append(0)
print(max(max(a),max(b)))


### FIXED CODE ###

N,C = map(int,input().split())
x1=[]
v1=[]

for i in range(N):
    x,v = map(int,input().split())
    x1.append(x)
    v1.append(v)
x2 = [C-x for x in x1]
v2 = [v for v in v1]
x2.reverse()
v2.reverse()

res1 = 0
res2 = 0
s1 = 0
s2 = 0
r1 = [0]
r2 = [0]
for i in range(N):
    s1 += v1[i]
    s2 += v2[i]
    res1 = max(res1,s1-x1[i])
    res2 = max(res2,s2-x2[i])
    r1.append(res1)
    r2.append(res2)

vl1 = [0]*(N+1)
vl2 = [0]*(N+1)
for i in range(N):
    vl1[i+1] = v2[i]+vl1[i]
    vl2[i+1] = v1[i]+vl2[i]
for i in range(N):
    vl1[i+1] -= 2*x2[i]
    vl2[i+1] -= 2*x1[i]



ans = 0
for i in range(N+1):
    res = vl1[i]+r1[N-i]
    if res > ans:
        ans = res
    res = vl2[i]+r2[N-i]
    if res > ans:
        ans = res

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

import math


def combination(n, r):
    if n <= 1:
        return 0
    elif n == 2:
        return 1
    else:
        return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


def count_list(lst):
    count_lst = [0] * (max(lst) + 1)

    for i in lst:
        count_lst[i] += 1

    return count_lst


def main():
    n = int(input())
    a_lst = list(map(int, input().split()))
    lst1 = count_list(a_lst)
    lst2 = [0] * len(lst1)
    for i in range(len(lst1)):
        lst2[i] = combination(lst1[i], 2)
    tmp = sum(lst2)

    for i in range(n):
        a = a_lst[i]
        tmp_tmp = tmp
        tmp -= lst2[a]
        tmp += combination(lst1[a] - 1, 2)
        print(tmp)
        tmp = tmp_tmp


if __name__ == '__main__':
    main()

### FIXED CODE ###

import math


def combination(n, r):
    if n <= 1:
        return 0
    elif n == 2:
        return 1
    else:
        return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


def count_list(lst):
    count_lst = [0] * (max(lst) + 1)

    for i in lst:
        count_lst[i] += 1

    return count_lst


def main():
    n = int(input())
    a_lst = list(map(int, input().split()))
    lst1 = count_list(a_lst)
    lst2 = [0] * len(lst1)
    for i in range(len(lst1)):
        lst2[i] = combination(lst1[i], 2)
    tmp = sum(lst2)

    for i in range(n):
        a = a_lst[i]
        print(tmp - (lst1[a] - 1))


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

H,N = map(int,input().split())
AB = [list(map(int,input().split())) for _ in range(N)]
INF = float('inf')
dp = [INF]*(H+1)
dp[0] = 0
for i in range(1,H+1):
  for k in AB:
    a = k[0]
    b = k[1]
    tmp = max(0,i-a)
    dp[i] = min(dp[i],dp[tmp]+b)
    
print(dp[H])

### FIXED CODE ###

H,N = map(int,input().split())
AB = [list(map(int,input().split())) for _ in range(N)]
INF = float('inf')
dp = [INF]*(H+1)
dp[0] = 0
for i in range(1,H+1):
  for k in AB:
    a = k[0]
    b = k[1]
    tmp = max(0,i-a)
    dp[i] = min(dp[i],dp[tmp]+b)
    
print(dp[H])
### BUGGY CODE ###

n, x, y = map(int, input().split())

inf = 100000000
G = [[inf for i in range(n)] for j in range(n)]

for i in range(n-1):
    G[i][i] = 0
    G[i][i+1] = 1
    G[i+1][i] = 1
    G[x-1][y-1] = 1
    G[y-1][x-1] = 1
    
v = [False]*n #visited
d = [0]*n #shortest distance

def getsmallindex():
    index = 0
    mn = inf
    for i in range(n):
        if d[i] < mn and v[i] == False:
            mn = d[i]
            index = i
    return index

def dijkstra(start):
    for i in range(n):
        d[i] = G[start][i]
    v[start] = True
    for i in range(n-1):
        current = getsmallindex()
        v[current] = True
        for j in range(n):
            if v[j] == False:
                if d[current] + G[current][j] < d[j]:
                    d[j] = d[current] + G[current][j]

s = [0]*n 
for i in range(n):
    v = [False]*n #visited
    d = [0]*n #shortest distance
    dijkstra(i)
    for k in range(1,n):
        for j in range(i,n):
            if d[j] == k:
                s[k] = s[k] + 1
    
for i in range(1,n):
    print(s[i])

        

### FIXED CODE ###


n, x, y = map(int, input().split())

d = [0]*(n-1)
for i in range(1, n+1):
    for j in range(i+1,n+1):
        c = min(j-i, abs(i-x)+1+abs(j-y))
        d[c-1] = d[c-1] + 1

for i in d:
    print(i)
### BUGGY CODE ###

from functools import lru_cache
from operator import itemgetter
from random import randint
from time import time


@lru_cache(maxsize=None)
def contract(aaa):
    if len(aaa) == 2:
        return sum(aaa)
    ans = 10 ** 18
    for i in range(1, len(aaa) - 1):
        ret = list(aaa[:i])
        ret.extend(aaa[i + 1:])
        ret[i - 1] += aaa[i]
        ret[i] += aaa[i]
        res = contract(tuple(ret))
        ans = min(ans, res)
    return ans


def greedy(aaa, order):
    ans = 10 ** 18
    contracted = set()
    for i, v in order:
        j = i
        for c in contracted:
            if c < i:
                j -= 1
        aj = aaa[j]
        aaa = aaa[:j] + aaa[j + 1:]
        aaa[j - 1] += aj
        aaa[j] += aj
        contracted.add(i)
        if len(aaa) <= 12:
            ans = min(ans, contract(tuple(aaa)))
            break
    return ans


def solve(aaa):
    if len(aaa) <= 12:
        return contract(tuple(aaa))
    order = sorted(enumerate(aaa[1:-1], start=1), key=itemgetter(1))
    ans = greedy(aaa, order)
    lim = time() + 1.9
    while time() < lim:
        i = randint(1, n - 4)
        order[i], order[i + 1] = order[i + 1], order[i]
        res = greedy(aaa, order)
        if res < ans:
            ans = res
        elif res == ans:
            if randint(0, 1) == 1:
                order[i], order[i + 1] = order[i + 1], order[i]
        else:
            order[i], order[i + 1] = order[i + 1], order[i]
    return ans


n = int(input())
aaa = list(map(int, input().split()))
ans = solve(aaa)
# ans = contract(tuple(aaa))
print(ans)


### FIXED CODE ###

from functools import lru_cache


def solve(n, aaa):
    @lru_cache(maxsize=None)
    def search_min(li, ri, lc, rc):
        w = ri - li
        base = aaa[li] * lc
        if w == 1:
            return base
        lrc = lc + rc
        if w == 2:
            return base + aaa[li + 1] * lrc
        if w == 3:
            a1, a2 = aaa[li + 1], aaa[li + 2]
            return base + (a1 + a2) * lrc + min(a1 * lc, a2 * rc)
        ret = min(search_min(li, i, lc, lrc) + search_min(i, ri, lrc, rc) for i in range(li + 1, ri))
        return ret

    return search_min(0, n - 1, 1, 1) + aaa[-1]


n = int(input())
aaa = list(map(int, input().split()))
print(solve(n, aaa))
### BUGGY CODE ###

import sys
import math
import numpy as np
stdin = sys.stdin
 
ni = lambda: int(ns())
na = lambda: list(map(int, input().split()))
ns = lambda: input()
H,W,D = na()
f= [list(map(int,input().split())) for i in range(H)]
#print(f)
f = np.array(f)

Q=int(input())
#累積和を求める
li = [0]*(H*W+2)
#print(H*W+2)
for i in range(1,D+1):
    #print('i=',i)
    li[i]=0
    h_=int(np.where(f==i)[0])
    w_=int(np.where(f==i)[1])
    for j in range(i+D,H*W+1,D):
        #print(j)
       
        li[j] = li[j-D]+abs(h_ - int(np.where(f==j)[0]))+abs(w_ - int(np.where(f==j)[1]))
        h_=int(np.where(f==j)[0])
        w_=int(np.where(f==j)[1])
        #print("diff",h_,w_)

        #print(j)
    
#print(li)
'''for i in range(1,26,4):
    print(i,li[i])
'''
# ここから計算
L = 17
R=25
#print(li[R]-li[L])
for i in range(Q):
    L,R = na()
    print(li[R]-li[L])



### FIXED CODE ###

import sys
import math
import numpy as np
stdin = sys.stdin
 
ni = lambda: int(ns())
na = lambda: list(map(int, input().split()))
ns = lambda: input()
H,W,D = na()
f= [list(map(int,input().split())) for i in range(H)]
#print(f)
f = np.array(f)
Q=int(input())
'''
li = [0]*(H*W+2)
for i in range(1,D+1):
    li[i]=0
    h_=int(np.where(f==i)[0])
    w_=int(np.where(f==i)[1])
    for j in range(i+D,H*W+1,D):
        h_n=int(np.where(f==j)[0])
        w_n=int(np.where(f==j)[1])
        li[j] = li[j-D]+abs(h_ - h_n)+abs(w_ - w_n)
        h_ = h_n
        w_ = w_n
for i in range(Q):
    L,R = na()
    print(li[R]-li[L])
'''

li ={}
for i in range(H):
    for j in range(W):
        li[f[i][j]]=[i+1,j+1]
res=[0]*(H*W+1)
for i in range(1,D+1):
    for j in range(i+D,W*H+1,D):
        #print("j",j)
        #print(li[j][0],li[j][1])
        res[j] = res[j-D] +abs(li[j-D][0]-li[j][0]) + abs(li[j-D][1]-li[j][1])
#print(res)
for i in range(Q):
    L,R = na()
    print(res[R]-res[L])