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

H,W,D=map(int,input().split());A=[list(map(int,input().split())) for _ in range(H)];Q=int(input());d=[0]*(H*W+1);g=[0]*(H*W+1)
for i in range(H):
  for j in range(W):d[A[i][j]]=[i,j]
for i in range(1,H*W-D+1):
  g[i]=abs(d[i+D][0]-d[i][0])+abs(d[i+D][1]-d[i][1])
for _ in range(Q):
  l,r=map(int,input().split());a=0
  while l<r:
    a+=g[l];l+=D
  print(a)

### FIXED CODE ###

H,W,D=map(int,input().split());A=[list(map(int,input().split())) for _ in range(H)];Q=int(input());d=[0]*(H*W+1);g=[0]*(H*W+1)
for i in range(H):
  for j in range(W):d[A[i][j]]=[i,j]
for i in range(1,H*W-D+1):
  g[i+D]=abs(d[i+D][0]-d[i][0])+abs(d[i+D][1]-d[i][1])+g[i]
for q in range(Q):
  l,r=map(int,input().split());print(g[r]-g[l])
### BUGGY CODE ###

N,K = [int(x) for x in input().split()]
count = [0]*(K+1)
ans = 0
mod = 1000000007
for i in range(K,0,-1):
    kosuu = ((K//i)**N) %mod
    if K // i >= 2:
        for j in range(K//i,1,-1):
            kosuu -= count[j*i]
    ans += (i*kosuu)
    count[i] = kosuu
print(ans%1000000007)

### FIXED CODE ###

N,K = [int(x) for x in input().split()]
count = [0]*(K+1)
ans = 0
mod = 1000000007
for i in range(K,0,-1):
    kosuu = pow(K//i,N,mod)
    if K // i >= 2:
        for j in range(K//i,1,-1):
            kosuu -= count[j*i]
    ans += i*kosuu
    count[i] = kosuu
print(ans%mod)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = 0
for i in range(n):
  l,r = 1,1
  while i-l > -1 and a[i-l] > a[i]:
    l += 1
  while i+r < n and a[i+r] > a[i]:
    r += 1
  ans += l*r*a[i]
print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
p = [0]*(n+1)
ans = 0
for i in range(n):
  p[a[i]] = i+1
l = [i-1 for i in range(n+2)]
l[0] = 0
r = [i+1 for i in range(n+2)]
r[-1] = n+1
for i in range(n,0,-1):
  ans += (p[i]-l[p[i]])*(r[p[i]]-p[i])*i
  l[r[p[i]]] = l[p[i]]
  r[l[p[i]]] = r[p[i]]
print(ans)
### BUGGY CODE ###

import sys
from collections import Counter
input=sys.stdin.readline
N=int(input())
d=Counter(list(input() for _ in range(N)))
L=[]
for k, v in d.items():
 if v == max(d.values()):
  L.append(k)
L.sort()
for i in L:
 print(i)

### FIXED CODE ###

n=int(input())
arr=[input() for _ in range(n)]
dic={}
for i in range(n): #各単語の出現回数を数える
 if arr[i] not in dic:
   dic[arr[i]]=1
 else:
   dic[arr[i]]+=1
largest=max(dic.values()) #最大の出現回数を求める
ans=[]
for keys in dic.keys():
 if dic[keys]==largest: #出現回数が最も多い単語を集計する
   ans.append(keys)
ans=sorted(ans) #単語を辞書順に並べ替えて出力する
for words in ans:
 print(words)
### BUGGY CODE ###

n,k = map(int,input().split())
xy = [list(map(int,input().split())) for _ in range(n)]
ans = float('inf')
for i in range(len(xy)):
    for j in range(i+1,len(xy)):
        x1 = min(xy[i][0],xy[j][0])
        x2 = max(xy[i][0],xy[j][0])
        for m in range(len(xy)):
            for l in range(m+1,len(xy)):
                y1 = min(xy[m][1],xy[l][1])
                y2 = max(xy[m][1],xy[l][1])
                points = 0
                for c in range(len(xy)):
                    x,y = xy[c]
                    if x1<=x<=x2 and y1<=y<=y2:
                        points+=1
                if points>=k:
                    ans = min(ans,(x2-x1)*(y2-y1))

print(ans)

### FIXED CODE ###

n,k = map(int,input().split())
x_y = [list(map(int,input().split())) for _ in range(n)]
x_y = sorted(x_y,key=lambda x:(x[0],x[1]))
ans = float('inf')
for i in range(n-1):
    for j in range(i+1,n):
        if j-i+1<k:
            continue
        dis_x = x_y[j][0]-x_y[i][0]
        y_x = x_y[i:j+1]
        y_x = sorted(y_x,key=lambda x:x[1])
        for l in range(len(y_x)-1):
            for m in range(l+1,len(y_x)):
                if m-l+1<k:
                    continue
                dis_y = y_x[m][1]-y_x[l][1]
                ans = min(ans,dis_x*dis_y)
print(ans)
### BUGGY CODE ###

ans = input()
Q = int(input())

for _ in range(Q):
    q = list(map(str,input().split()))
    if q[0] == '1':
        ans = ans[::-1]
    else:
        if q[1] == '1':
            ans = q[2] + ans
        else:
            ans = ans + q[2]
print(ans)


### FIXED CODE ###

from collections import deque
s = list(input())
ans = deque(s)
Q = int(input())
is_reverse = False
for _ in range(Q):
    q = list(map(str,input().split()))
    if q[0] == '1':
        is_reverse = True ^ is_reverse # 反転
        #ans = ans[::-1]
    else:
        if is_reverse: # 反転してた場合
            if q[1] == '1':
                #ans = ans + q[2]
                ans.append(q[2])
            else:
                #ans = q[2] + ans
                ans.appendleft(q[2])
        else:
            if q[1] == '1':
                #ans = q[2] + ans
                ans.appendleft(q[2])
            else:
                #ans = ans + q[2]
                ans.append(q[2])
ans_s = ''.join(ans)
if is_reverse:
    print(ans_s[::-1])
else:
    print(ans_s)

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

n = int(input())
a = list(map(int,input().split()))
a.sort()
st = min(a)
ed = max(a)
count = a.count(st) + a.count(st+1) + a.count(st+2)
mx = count
for i in range(3,ed-st+1):
  count = count + a.count(st+i) -a.count(st+i-3)
  if count > mx:
    mx = count
print(mx)

### FIXED CODE ###

n = int(input())
x = [0]*100001
a = list(map(int,input().split()))
m = 0
ma = 0
for i in range(n):
    x[a[i]]+=1
for i in range(100001-2):
    m=x[i]+x[i+1]+x[i+2]
    if m>ma:
        ma=m
print(ma)
### BUGGY CODE ###

n = int(input())
p = list(map(float, input().split()))

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

for i in range(1, n+1):
    for j in range(0, i+1):
        if j > 0:
            dp[i][j] = dp[i-1][j]*(1-p[i-1])+dp[i-1][j-1]*p[i-1]
        else :
            dp[i][j] = dp[i-1][j]*(1-p[i-1])

ans = 0
for j in range((n+1)//2, n+1):
    ans += dp[n][j]
print(ans)


### FIXED CODE ###

import numpy as np

n = int(input())
p = list(map(float, input().split()))

dp = np.zeros(n+1)
dp[0] = 1

for i in range(1, n+1):
    dp[1:] = dp[:-1]*p[i-1]+dp[1:]*(1-p[i-1])

print(dp[(n+1)//2])
### BUGGY CODE ###

s= str(input().strip())
K= int(input().strip())
parts = []
for i in range(len(s)+1):
    for j in range(i+1,len(s)+1):
        flg = 0
        for k in parts:
            if s[i:j] == k:
                flg = 1
        if flg == 0:
            parts.append(s[i:j])
        
v = sorted(parts)
print(v[K-1])

### FIXED CODE ###

s= str(input().strip())
K= int(input().strip())
parts = []
for i in range(len(s)+1):
    for j in range(i+1,len(s)+1):
        flg = 0
        if j-i > K:
            break
        parts.append(s[i:j])
v = sorted(parts)
vv = [v[0]]
tmp = v[0]
for k in range(1,len(v)):
    if v[k]!=tmp:
        vv.append(v[k])
        tmp = v[k]
    if len(vv)==K:
        break
        
print(vv[K-1])
### BUGGY CODE ###

from sys import stdin
import numpy as np


def merge_sort(lst, low, high):
    if low >= high:
        return
    mid = int((low+high)/2)
    merge_sort(lst, low, mid)
    merge_sort(lst, mid+1, high)
    for i in range(low, mid+1):
        tmp_array[i] = lst[i]
    j = high
    for i in range(mid+1, high+1):
        tmp_array[i] = lst[j]
        j -= 1
    i = low
    j = high
    for k in range(low, high+1):
        if tmp_array[i] <= tmp_array[j]:
            lst[k] = tmp_array[i]
            i += 1
        else:
            lst[k] = tmp_array[j]
            j -= 1


S = stdin.readline().rstrip()
N = len(S)
Sp = S

res_map = [0 for _ in range(N)]

aa_list2 = [1]
for i in range(1,N):
    aa_list2.append((aa_list2[i-1]*10)%2019)

tmp_array = [None for _ in range(N)]
res_map[N-1] = int(S[N-1])
index=1
for i in range(N-2,-1,-1):
    res_map[i] = (int(S[i])*aa_list2[index] + res_map[i+1])%2019
    index+=1
#merge_sort(res_map,0,N-1)
#res_map = list(np.sort(np.array(res_map)))
res_map.sort()
temp_num=int(res_map[0])
index=1
tot = 0

#for i in range(1,N):
#    if temp_num==res_map[i]:
#        index+=1
#        continue
#    else:
#        if temp_num==0:
#            tot += int(index*(index+1)/2)
#        elif index>1:
#            tot += int(index*(index-1)/2)
#            #tot += index/2
#        index=1
#        temp_num=res_map[i]


for i in range(2018):
    num = np.sum(np.array(res_map)==i)
    if i ==0:
        num+=1
    tot += int(num*(num-1)/2)
    

print(tot)



### FIXED CODE ###

from sys import stdin

S = stdin.readline().rstrip()
N = len(S)
Sp = S

res_map = [0 for _ in range(N)]

aa_list2 = [1]
for i in range(1,N):
    aa_list2.append((aa_list2[i-1]*10)%2019)

res_map[N-1] = int(S[N-1])
index=1


for i in range(N-2,-1,-1):
    res_map[i] = (int(S[i])*aa_list2[index] + res_map[i+1])%2019
    index+=1

aa_table = [0 for i in range(2019)]
for i in range(len(res_map)):
    aa_table[res_map[i]]+=1

aa_table[0]+=1

tot = 0
for i in range(2019):
    tot+=int((aa_table[i]-1)*aa_table[i]/2)

print(tot)
### BUGGY CODE ###

import numpy as np


N, K, Q = map(int, input().split())
A = np.array([int(input()) for i in range(Q)])

initial_arr = np.ones(N) * K

for i in range(Q):
    tmp = np.ones(N)
    tmp[A[i]-1] = 0
    initial_arr = initial_arr - tmp

for i in initial_arr:
    if i > 0:
        print('Yes')
    else:
        print('No')


### FIXED CODE ###

N, K, Q = map(int, input().split())
A = [int(input()) for i in range(Q)]

victory_cnt = [0] * N 

for i in range(Q):
    victory_cnt[A[i]-1] += 1

for v in victory_cnt:
    if (Q-v) >= K:
        print('No')
    else:
        print('Yes')
### BUGGY CODE ###

X = input()

while X.count("ST"):
    X = X.replace("ST", "")

print(len(X))


### FIXED CODE ###

X = input()

ans = ["foo"]
for i in range(len(X)):
    ans.append(X[i])
    if ans[-2] == "S" and ans[-1] == "T":
        ans.pop()
        ans.pop()

print(len(ans) - 1)
### BUGGY CODE ###

N,M=map(int,input().split())

base=M//N

for i in range(base,0,-1):
    if M%i==0:
        print(i)
        break



### FIXED CODE ###

N,M=map(int,input().split())

base=M//N
li=[]


for i in range(1,int(pow(M,1/2))+1):
    if i<=base and M%i==0:
        li.append(i)
    if M%i==0 and M//i<=base:
        li.append(M//i)

print(max(li))
### BUGGY CODE ###

N, K, Q = map(int, input().split())
A = {}

P = [K] * N
for i in range(Q):
    tmp = int(input()) - 1
    for j in range(N):
        if j != tmp:
            P[j] -= 1
for n in range(N):
    ans = 'Yes'
    if P[n] <= 0:
        ans = 'No'
    print(ans)

### FIXED CODE ###

N, K, Q = map(int, input().split())

P = [0] * N
for i in range(Q):
    tmp = int(input()) - 1
    P[tmp] += 1

sumP = sum(P)
for n in range(N):
    ans = 'No'
    total = sumP - P[n]
    if  K - total > 0:
        ans = 'Yes'
    print(ans)
### BUGGY CODE ###

import math 
k=int(input())
ans=0
for i in range(1,k+1):
  for j in range(1,k+1):
    for k in range(1,k+1):
      ans+=(math.gcd(math.gcd(i,j),k))
print(ans)


### FIXED CODE ###

import math 
k=int(input())
ans=0
for i in range(1,k+1):
  for j in range(1,k+1):
    for k in range(1,k+1):
      ans+=(math.gcd(math.gcd(i,j),k))
print(ans)
### BUGGY CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
import numpy as np

def scores(c, s, t):
    last = [0] * 26
    V = []
    lastv = 0
    for d, i in enumerate(t):
        last[i] = d+1
        v = s[d*26+i]
        sub = sum([c[j]*(d+1-last[j]) for j in range(26)])
        # print(v, sub)
        lastv += v-sub
        V.append(lastv)
    return V


def main():
    D, *cs = map(int, read().split())
    c = cs[:26]
    s = cs[26:]

    b = 0
    ans = []
    for d in range(D):
        maxi = 0
        score_max = -1000000000
        for i in range(26):
            if scores(c, s, ans + [i])[-1] > score_max:
                maxi = i
        ans.append(maxi)
        b += 26

    ans = [a+1 for a in ans]
    print(*ans, sep='\n')

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
import numpy as np

def scores(c, s, t):
    last = [0] * 26
    V = []
    lastv = 0
    for d, i in enumerate(t):
        last[i] = d+1
        v = s[d*26+i]
        sub = sum([c[j]*(d+1-last[j]) for j in range(26)])
        # print(v, sub)
        lastv += v-sub
        V.append(lastv)
    return V


def main():
    D, *cs = map(int, read().split())
    c = cs[:26]
    s = cs[26:]

    b = 0
    ans = []
    for d in range(D):
        maxi = 0
        for i in range(26):
            if s[b+i] > s[b+maxi]:
                maxi = i
        ans.append(maxi + 1)
        b += 26

    print(*ans, sep='\n')

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

N,K = map(int, input().split())
P = list(map(int, input().split()))
L = []
for i in P:
    if i % 2 == 0:
        L.append((i+1)*(i//2)*(1/i))
    else:
        L.append(((i+1)*(i//2)+(i//2+1))*(1/i))
n = 0
for i in range(N-K+1):
    n = max(n,sum(L[i:i+K]))
print(n)

### FIXED CODE ###

N,K = map(int, input().split())
P = list(map(int, input().split()))
L = []
S = [0]
for i in range(N):
    if P[i] % 2 == 0:
        L.append((P[i]+1)*(P[i]//2)*(1/P[i]))
    else:
        L.append(((P[i]+1)*(P[i]//2)+(P[i]//2+1))*(1/P[i]))
    S.append(L[-1]+S[-1])
n = 0
for i in range(N-K+1):
    n = max(n,S[i+K]-S[i])
print(n)
### BUGGY CODE ###

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

ans_1 = S[1:].count("E")
ans_2 = N
for i in range(N):
    count = S[:i].count("W") + S[i+1:].count("E")
    if ans_2 > count:
        ans_2 = count
ans_3 = S[:N-1].count("W")

print(min(ans_1, ans_2, ans_3))

### FIXED CODE ###

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

left = [0 for i in range(N)]
right = [0 for i in range(N)]
for i in range(1, N):
    if S[i-1] == "W":
        left[i] = left[i-1] + 1
    else:
        left[i] = left[i-1]
for i in range(N-1):
    if S[(N-1)-i] == "E":
        right[(N-2)-i] = right[(N-1)-i] + 1
    else:
        right[(N-2)-i] = right[(N-1)-i]

ans = left[0] + right[0]
for i in range(1, N):
    count = left[i] + right[i]
    if ans > count:
        ans = count
print(ans)
### BUGGY CODE ###

n = int(input())
s = list(input())
m = n
for i in range(n):
    w = s[:i]
    e = s[i + 1:]
    count = w.count('W') + e.count('E')
    if m > count:
        m = count
print(m)


### FIXED CODE ###

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

reS = S[::-1]

wSum = [0 for i in range(N)]
eSum = [0 for i in range(N)]

for i in range(N):
    if i == 0:
        if S[i] == 'W':
            wSum[i] = 1
        if reS[i] == 'E':
            eSum[i] = 1
    else:
        if S[i] == 'W':
            wSum[i] = wSum[i-1] + 1
        else:
            wSum[i] = wSum[i-1]
        if reS[i] == 'E':
            eSum[i] = eSum[i-1] + 1
        else:
            eSum[i] = eSum[i-1]

eSum = eSum[::-1]

cost = eSum[1]

for i in range(1,N):
    if i == N - 1:
        if cost > wSum[N-2]:
            cost = wSum[N-2]
    else:
        if cost > wSum[i-1] + eSum[i+1]:
            cost = wSum[i-1] + eSum[i+1]
print(cost)
### BUGGY CODE ###

N = int(input())
S = []
for i in range(N):
    S.append(input())

#S.sort()

dic = list((set(S)))
times = [0] * len(dic)

for s in S :
    for i in range(len(dic)):
        if dic[i] == s:
            times[i] += 1

ans = [0] * len(dic)
ma = max(times)

s_ans = []

for a in range(len(dic)):
    if times[a] == ma:
        s_ans.append(dic[a])

s_ans.sort()

for j in range(len(s_ans)):
    print(s_ans[j])



### FIXED CODE ###

N = int(input())
S = []
for i in range(N):
    S.append(input())

S.sort()

dic = list((set(S)))
dic.sort()
times = [0] * len(dic)
aa=0

for s in S :
    if dic[aa] == s:
        times[aa] += 1
    else:
        aa += 1
        times[aa] += 1

ans = [0] * len(dic)
ma = max(times)

s_ans = []

for a in range(len(dic)):
    if times[a] == ma:
        s_ans.append(dic[a])

s_ans.sort()

for j in range(len(s_ans)):
    print(s_ans[j])
### BUGGY CODE ###

import sys
import bisect
input = sys.stdin.readline

def main():
    n=int(input())
    h = list(map(int,input().split()))

    ans="Yes"

    for i in range(n-1):
        a=n-i-1
        for j in range(a):
            if(h[i]>=h[i+j+1]+2):
                ans="No"
            if(ans=="No"):
                break
        if(ans=="No"):
            break
        
    
    print(ans)
    
main()

### FIXED CODE ###

import sys
import bisect
input = sys.stdin.readline

def main():
    n=int(input())
    h = list(map(int,input().split()))

    ans="Yes"
    m=0

    for i in range(n):
        if(m>=h[i]+2):
            ans="No"
        else:
            m=max(m,h[i])
        if(ans=="No"):
            break
        
    print(ans)
    
main()
### BUGGY CODE ###

n = int(input())

cnt = [1] + [2] * (n - 1)
for i in range(2, n // 2 + 1):
    for j in range(i - 1 + i, n, i):
        cnt[j] += 1
print(sum((i + 1) * cnt[i] for i in range(n)))


### FIXED CODE ###

n = int(input())

cnt = [1] * n
for i in range(2, n + 1):
    for j in range(i - 1, n, i):
        cnt[j] += 1
print(sum((i + 1) * cnt[i] for i in range(n)))
### BUGGY CODE ###

K = int(input())
total = 0

def gdc(x,y):
  if x%y==0:
    return y
  return gdc(y, x%y)

for a in range(K):
  for b in range(K):
    for c in range(K):
      total += gdc(c+1, gdc(b+1, a+1))
print(total)


### FIXED CODE ###

K = int(input())
total = 0

def gdc(x,y):
  if x%y==0:
    return y
  return gdc(y, x%y)

for a in range(K):
  for b in range(a,K):
    for c in range(b,K):
      if a==b and b==c:
        total += gdc(c+1, gdc(b+1, a+1))
      elif a==b or b==c or a==c:
        total += 3*gdc(c+1, gdc(b+1, a+1))
      else:
        total += 6*gdc(c+1, gdc(b+1, a+1))
print(total)
### BUGGY CODE ###

import sys

input = sys.stdin.buffer.readline
n = int(input())
A = [list(map(int, input().split())) for _ in range(n)]
mod = 10 ** 9 + 7
dp = [0] * (pow(2, n))
dp[0] = 1
# dp[i][j] 男i人に対して女の集合Sが合致
for s in range(pow(2, n)):
    otoko = bin(s).count("1")
    i = otoko
    for j in range(n):
        if (s >> j) & 1 == 0:
            if A[i][j] == 1:
                ns = s | 1 << j
                dp[ns] += dp[s]
                dp[ns] %= mod
print(dp[pow(2, n) - 1])


### FIXED CODE ###

import sys

input = sys.stdin.buffer.readline
n = int(input())
A = [list(map(int, input().split())) for _ in range(n)]
mod = 10 ** 9 + 7
dp = [0] * (pow(2, n))
dp[0] = 1
# dp[i][j] 男i人に対して女の集合Sが合致
bitcnt = [0] * (pow(2, n) + 1)
for s in range(pow(2, n)):
    # otoko = bin(s).count("1")
    bitcnt[s] = bitcnt[s // 2] + s % 2
    i = bitcnt[s]
    for j in range(n):
        if (s >> j) & 1 == 0:
            if A[i][j] == 1:
                ns = s | 1 << j
                dp[ns] += dp[s]
                dp[ns] %= mod
print(dp[pow(2, n) - 1])
### BUGGY CODE ###

t,r,g=map(int,input().split())
d=[[float("INF")]*t for i in range(t)]
for i in range(t):
    d[i][i]=0
gl=list(map(int,input().split()))
for j in range(r):
    x,y,c=map(int,input().split())
    d[x-1][y-1]=c
    d[y-1][x-1]=c
for i in range(t):
    for j in range(t):
        for k in range(t):
            d[i][j]=min(d[i][j],d[i][k]+d[k][j])
from itertools import permutations as pe
ans=float("INF")
for i in pe(gl,r=None):
    #rは長さ、Noneでiteraterの長さ
    p=0
    for k,j in zip(i,i[1:]):
        p+=d[k-1][j-1]
    ans=min(ans,p)
print(ans)

### FIXED CODE ###

t,r,g=map(int,input().split())
d=[[float("INF") for ccc in range(t)] for i in range(t)]
for i in range(t):
    d[i][i]=0
gl=list(map(int,input().split()))
for j in range(r):
    x,y,c=map(int,input().split())
    d[x-1][y-1]=c
    d[y-1][x-1]=c
for i in range(t):
    for j in range(t):
        for k in range(t):
            d[k][j]=min(d[k][j],d[k][i]+d[i][j])
from itertools import permutations as pe
ans=float("INF")
for G in pe(gl):
    p=0
    for qw in range(g-1):
        p+=d[G[qw]-1][G[qw+1]-1]
    ans=min(ans,p)
print(ans)
### BUGGY CODE ###

n = int(input())
numlist = [int(_) for _ in input().split()]
setnum = set(numlist)
dicnum = {}
nsum = 0

for i in setnum:
    dicnum[i] = numlist.count(i)
    if dicnum[i] >= 2:
        nsum += dicnum[i]*(dicnum[i]-1)//2
    
for j in range(n):
    ans = nsum
    cal = dicnum[numlist[j]]
    if cal >= 2:
        ans = ans - (cal-1)
    print(ans)

### FIXED CODE ###

n = int(input())
numlist = [int(_) for _ in input().split()]
numdic = {}
nsum = 0

for i in range(n):
    if numlist[i] in numdic:
        numdic[numlist[i]] += 1
    else:
        numdic[numlist[i]] = 1

for k in numdic:
    nsum += numdic[k] * (numdic[k] - 1) // 2

for j in range(n):
    ans = nsum
    cal = numdic[numlist[j]]
    if cal >= 2:
        ans = ans - (cal-1)
    print(ans)
### BUGGY CODE ###

import math

q = int(input())

def sosu(a):
    for i in range(2,math.ceil(math.sqrt(a))+1):
        if a%i == 0:
            dic[a] = 0
            break
    else:
        dic[a] = 1

dic = {1:0,2:1,3:1}
for i in range(q):
    l,r = map(int,input().split())
    ans = 0
    for j in range(l,r+1,2):
        if j not in dic:
            sosu(j)
        if (j+1)//2 not in dic:
            sosu((j+1)//2)
        if dic[j] == 1 and dic[(j+1)//2] == 1:
            ans += 1
    print(ans)
        



### FIXED CODE ###

import math

q = int(input())

def is_prime(a):
    if a == 1:
        return False
    for i in range(2,int(math.sqrt(a)+1)):
        if a%i == 0:
            return False
    else:
        return True

s = [0 for i in range(0,100001)]
for i in range(3,100001,2):
    if is_prime(i) and is_prime((i+1)//2):
        s[i] = 1

s2 = [0 for i in range(0,100001)]
tmp = 0
for i in range(100001):
    tmp += s[i]
    s2[i] = tmp

for i in range(q):
    l,r = map(int,input().split())
    ans = s2[r] - s2[l-1]
    print(ans)
### BUGGY CODE ###

k=int(input())

def gcd(l,m,n):
  f=min(l,m,n)
  while l%f!=0 or m%f!=0 or n%f!=0:
    f=f-1
  return f

sum=0
for l in range(1,k+1):
  for m in range(1,k+1):
    for n in range(1,k+1):
      sum=sum+gcd(l,m,n)

print(sum)

### FIXED CODE ###

k=int(input())
 
def gcd(l,m,n):
  f=min(l,m,n)
  while l%f!=0 or m%f!=0 or n%f!=0:
    f=f-1
  return f
 
sum=0
for l in range(1,k+1):
  for m in range(l,k+1):
    for n in range(m,k+1):
      if l==m==n:
        sum=sum+gcd(l,m,n)
      elif l==m or m==n:
        sum=sum+gcd(l,m,n)*3
      else:
        sum=sum+gcd(l,m,n)*6
 
print(sum)
### BUGGY CODE ###

k,s = map(int,input().split())
cnt=0
for x in range(k+1):
    for y in range(k+1):
        for z in range(k+1):
            if (x+y+z==s):
                cnt=cnt+1
print(cnt)

### FIXED CODE ###

k,s = map(int,input().split())
cnt=0
for x in range(k+1):
    for y in range(k+1):
        z = s-x-y
        if (z>=0)&(z<=k):
            cnt=cnt+1
print(cnt)
### BUGGY CODE ###

import itertools
import math
n = int(input())

lst = [_ for _ in range(1, n+1)]
lst2 = list(itertools.permutations(lst, 3))
lst3 = list(itertools.permutations(lst, 2))
l2 = sum([math.gcd(math.gcd(_[0],_[1]),_[2]) for _ in lst2])
l3 = sum([math.gcd(_[0], _[1]) for _ in lst3]) 
l4 = sum(lst)

ans = l2 + l3 * 3 + l4

print(ans)


### FIXED CODE ###

import itertools
import math
n = int(input())

lst = [_ for _ in range(1, n+1)]
lst2 = list(itertools.product(lst, repeat=2))

lst3 = [math.gcd(_[0], _[1]) for _ in lst2]

lst4 = list(itertools.product(lst3, lst))

lst5 = [math.gcd(_[0], _[1]) for _ in lst4]

print(sum(lst5))