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

import sys

def main():
	readline = sys.stdin.readline

	#s = tuple(input())
	s = input()
	length = len(s)

	dp = [[0]*13 for _ in range(length)]
	MOD = 10**9+7

	if s[-1] == '?':
		for i in range(10):
			dp[0][i] = 1
	else:
		dp[0][int(s[-1])] = 1

	a = 1
	for i in range(1,length):
		a = 10 * a % 13
		if s[-(i+1)] != '?':
			num = int(s[-(i+1)])
			for j in range(13):
				dp[i][(a*num+j)%13] += dp[i-1][j] % MOD
		else:
			num = (10**i) % 13
			#a = 0
			for j in range(10):
				for k in range(13):
					dp[i][(a*j+k)%13] += dp[i-1][k] % MOD
				#a += num

	print(dp[-1][5] % MOD)

if __name__ == '__main__':
	main()

### FIXED CODE ###

INF = 10 ** 9 + 7

S = input()
# dp[i][j]はうしろからi桁を13で割った余りがjであるものの個数
dp = [[0] * 13 for _ in range(len(S) + 1)]
dp[0][0] = 1
mul = 1

for i in range(len(S)):
    x = S[-(i + 1)]
    if x == "?":
        for k in range(10):
            for j in range(13):
                dp[i + 1][(mul * k + j) % 13] += dp[i][j]
                dp[i + 1][(mul * k + j) % 13] %= INF
    else:
        k = int(x)
        for j in range(13):
            dp[i + 1][(mul * k + j) % 13] += dp[i][j]
            dp[i + 1][(mul * k + j) % 13] %= INF
    mul = mul * 10 % 13  # 計算量削減のためここで13で割っている

print(dp[len(S)][5])
### BUGGY CODE ###

N, K = [int(i) for i in input().split()]
h = [int(i) for i in input().split()]

dp = [float('inf')] * N
dp[0] = 0
for i in range(1, N):
    for k in range(1, K+1):
        if i - k >= 0:
            dp[i] = min(dp[i], dp[i-k]+abs(h[i]-h[i-k]))
print(dp[N-1])

### FIXED CODE ###

import sys
def input():
    return sys.stdin.readline()
    
N, K = [int(i) for i in input().split()]
h = [int(i) for i in input().split()]

dp = [float('inf')] * N
dp[0] = 0
for i in range(1, N):
    for k in range(1, min(K+1, i+1)):
        dp[i] = min(dp[i], dp[i-k]+abs(h[i]-h[i-k]))
print(dp[N-1])
### BUGGY CODE ###


def examD():
    N, W = LI()
    w = [0]*N
    v = [0]*N
    w[0], v[0] = LI()
    wbasic = w[0]
    for i in range(1,N):
        a, b = LI()
        w[i] = a-wbasic
        v[i] = b
    w[0] = 0
    dp =[[[0]*(3*N+1) for _ in range(N+1)]for _ in range(N+1)]
    for i in range(N):
        for j in range(N+1):
            for k in range(3*N+1):
                dp[i+1][j][k] = max(dp[i][j][k], dp[i+1][j][k])
                if w[i]<=k and j>=1:
                    if j*wbasic+k<=W:
                        dp[i+1][j][k] = max(dp[i][j-1][k-w[i]]+v[i], dp[i+1][j][k])
    ans = 0
    for v in dp[N]:
        ans = max(ans,max(v))
#        print(v)
    print(ans)


import sys
import copy
import bisect
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

examD()


### FIXED CODE ###


def examD():
    N, W = LI()
    w = [0]*N
    v = [0]*N
    w[0], v[0] = LI()
    wbasic = w[0]
    for i in range(1,N):
        a, b = LI()
        w[i] = a-wbasic
        v[i] = b
    w[0] = 0
    dp =[[[0]*(3*N+1) for _ in range(N+1)]for _ in range(N+1)]
    for i in range(N):
        for j in range(N+1):
            for k in range(3*N+1):
                dp[i+1][j][k] = max(dp[i][j][k], dp[i+1][j][k])
                if w[i]<=k and j>=1:
                    if j*wbasic+k<=W:
                        dp[i+1][j][k] = max(dp[i][j-1][k-w[i]]+v[i], dp[i+1][j][k])
    ans = 0
    for v in dp[N]:
        ans = max(ans,max(v))
#        print(v)
    print(ans)


import sys
import copy
import bisect
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

examD()
### BUGGY CODE ###

from collections import defaultdict
from numba import jit
from collections import Counter

n = int(input())
a = list(map(int, input().split()))
arr = defaultdict(int)
for k, v in Counter(a).items():
    arr[k] = v
q = int(input())
bc = []
for _ in range(q):
    b, c = map(int, input().split())
    bc.append((b, c))


@jit('void(i8, i8[:], i8[:])')
def solve(n, arr, bc):
    for b, c in bc:
        arr[c] += arr[b]
        arr[b] = 0
        print(sum([x * y for x, y in arr.items()]))


solve(n, arr, bc)

### FIXED CODE ###

from collections import defaultdict
from collections import Counter

n = int(input())
a = list(map(int, input().split()))
arr = defaultdict(int)
for k, v in Counter(a).items():
    arr[k] = v
q = int(input())
bc = []
for _ in range(q):
    b, c = map(int, input().split())
    bc.append((b, c))

whole = sum([x * y for x, y in arr.items()])

for b, c in bc:
    arr[c] += arr[b]
    tmp = arr[b]
    arr[b] = 0
    whole += (c - b) * tmp
    print(whole)
### BUGGY CODE ###

s=list(input())
N=len(s)
n=0
while len(set(s))>1:
    if s[n]!=s[n+1]:
        del s[n+1]
        del s[n]
        n=0
    elif len(s)==2:break
    else:n+=1
print(N-len(s))

### FIXED CODE ###

s=list(input())
n=len(s)
zero=s.count("0")
one=s.count("1")
if n==1:print(0)
else:print(2*min(zero,one))
### BUGGY CODE ###

H,W,M = map(int,input().split())
P = [0]*(H+1)
Q = [0]*(W+1)
A = [[0 for j in range(W+1)] for i in range(H+1)]
for k in range(M):
  a,b = map(int,input().split())
  P[a] += 1
  Q[b] += 1
  A[a][b] = 1
Pmax = max(P)
Qmax = max(Q)
ans = Pmax+Qmax-1
#print(P,Q,A,Pmax,Qmax,ans)
Pindex = [i for i, v in enumerate(P) if v == Pmax]
Qindex = [i for i, v in enumerate(Q) if v == Qmax]
key = 0
for x in Pindex:
  for y in Qindex:
    if A[x][y] == 0:
      ans += 1
      key = 1
      break
  if key == 1:
    break
print(ans)

### FIXED CODE ###

H,W,M = map(int,input().split())
P = [0]*(H+1)
Q = [0]*(W+1)
A = set()
for k in range(M):
    a,b = map(int,input().split())
    P[a] += 1
    Q[b] += 1
    A.add((a,b))
Pmax = max(P)
Qmax = max(Q)
Pindex = []
Qindex = []
for i in range(H+1):
    if P[i] == Pmax:
        Pindex.append(i)
for i in range(W+1):
    if Q[i] == Qmax:
        Qindex.append(i)
ans = Pmax+Qmax-1
key = 0
for x in Pindex:
  for y in Qindex:
    if (x,y) not in A:
      ans += 1
      key = 1
      break
  if key == 1:
    break
print(ans)
### BUGGY CODE ###

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

from math import sqrt
from collections import Counter

def prime_factorization(n):
    factor = []
    f = 2
    while n > 1:
        if n % f == 0:
            factor.append(f)
            n /= f
        else:
            f += 1
    return factor

p = prime_factorization(P)
c = Counter(p)

l = []
j = []
for k, v in c.items():
    if N <= v:
        l.append(k)
        j.append(v//N)
ans = 1
for i,v in zip(l,j):
    ans *= i**v

print(ans)


### FIXED CODE ###

from collections import Counter

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

def prime_factorization(n):
    factor = []
    f = 2
    while f ** 2 <= n:
        if n % f == 0:
            factor.append(f)
            n //= f
        else:
            f += 1
    if n > 1:
        factor.append(n)
    return factor

p = prime_factorization(P)
c = Counter(p)

l = []
j = []
for k, v in c.items():
    if N <= v:
        l.append(k)
        j.append(v//N)
ans = 1

for i,v in zip(l,j):
    ans *= i**v

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

n = int(input())
a = list(map(int, input().split()))
q = int(input())
xy = [map(int, input().split()) for _ in range(q)]
b, c = [list(i) for i in zip(*xy)]

stuck_b = []
stuck_c = []
stuck_sum = []

sum = 0

for cnt_q in range(q):
    sum = 0
    if len(stuck_b) > 0:
        if stuck_b[cnt_q] == b[cnt_q] and stuck_c[cnt_q] == c[cnt_q]:
            print(stuck_sum[cnt_q])
        else:
            for cnt_n in range(n):
                if a[cnt_n] == b[cnt_q]:
                    a[cnt_n] = c[cnt_q]
            for num in range(n):
                sum += a[num]
            print(sum)
    else:
        for cnt_n in range(n):
            if a[cnt_n] == b[cnt_q]:
                a[cnt_n] = c[cnt_q]
        for num in range(n):
            sum += a[num]
        print(sum)


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
q = int(input())
xy = [map(int, input().split()) for _ in range(q)]
b, c = [list(i) for i in zip(*xy)]

ans = 0

sum_all = 0
for cnt in range(n):
    sum_all += a[cnt]

a = sorted(a)
list_a_num = [0]*(10**5 + 1)
for cnt in range(n):
    list_a_num[a[cnt]] += 1

for cnt in range(q):
    sum_all += (c[cnt] - b[cnt]) * list_a_num[b[cnt]]
    list_a_num[c[cnt]] += list_a_num[b[cnt]]
    list_a_num[b[cnt]] = 0
    print(sum_all)
### BUGGY CODE ###

N = int(input())
a=0
flag=0
for i in range(1,N+1):
    a+=(7*10**(i-1))%N
    if a>N:
        a-=N
    if a==N:
        a=0
    if a==0:
        print(i)
        flag=1
        break
if flag==0:
    print(-1)

### FIXED CODE ###

N = int(input())
a=0
flag=0
for i in range(1,N+1):
    a=(a*10+7)%N   
    if a==0:
        print(i)
        flag=1
        break

if flag==0:
    print(-1)
### BUGGY CODE ###

mod = 10**9 + 7
N = int(input())
A = list(map(int, input().split()))
ans = 0
loop_count = len(format(max(A), "b"))

for i in range(loop_count):
    tmp = 0
    for ai in A:
        if ((1 << i) & ai) > 0:
            tmp += 1
    ans += (1 << i) * tmp * (N - tmp) % mod
print(ans % mod)


### FIXED CODE ###

mod = 10**9 + 7
N = int(input())
A = list(map(int, input().split()))
ans = 0
loop_count = len(format(max(A), "b"))

for i in range(loop_count):
    tmp = 0
    for ai in A:
        if ((1 << i) & ai) > 0:
            tmp += 1
    ans += (1 << i) * tmp * (N - tmp) % mod
print(ans % mod)
### BUGGY CODE ###

from bisect import bisect
from time import time

st_time = time()
N = int(input())
src = list(map(int,input().split()))

cums = [0]
for a in src:
    cums.append(cums[-1] + a)

ans = cums[-1] * 999
c = bisect(cums, cums[-1]//2)
d = 1
while time() - st_time < 1.9:
    if abs(d) >= N: break
    if 2 <= c <= N-2:
        b1 = bisect(cums[:c], cums[c]//2)
        b2 = bisect(cums[c:], (cums[c]+cums[-1])//2) + c
        pq_cands = []
        for i in (b1,b1-1):
            if not 0 < i < c: continue
            p = cums[i]
            q = cums[c] - cums[i]
            pq_cands.append((p,q))
        rs_cands = []
        for i in (b2,b2-1):
            if not c < i < N: continue
            r = cums[i] - cums[c]
            s = cums[-1] - cums[i]
            rs_cands.append((r,s))
        for p,q in pq_cands:
            for r,s in rs_cands:
                mn = min(p,q,r,s)
                mx = max(p,q,r,s)
                ans = min(ans, mx-mn)
    c += d
    d = (abs(d)+1) * [1,-1][d%2]
print(ans)

### FIXED CODE ###

N = int(input())
src = list(map(int,input().split()))

cums = [0]
for a in src:
    cums.append(cums[-1] + a)

ps = [None] * (N+1)
qs = [None] * (N+1)
rs = [None] * (N+1)
ss = [None] * (N+1)

l = 1
for r in range(2,N-1):
    p1 = cums[l]
    q1 = cums[r] - cums[l]
    d1 = abs(p1-q1)
    while l < r:
        p2 = cums[l+1]
        q2 = cums[r] - cums[l+1]
        d2 = abs(p2-q2)
        if d2 > d1: break
        l += 1
        p1,q1,d1 = p2,q2,d2
    ps[r] = p1
    qs[r] = q1

r = N-1
for l in range(N-2,1,-1):
    r1 = cums[r] - cums[l]
    s1 = cums[N] - cums[r]
    d1 = abs(r1-s1)
    while l < r:
        r2 = cums[r-1] - cums[l]
        s2 = cums[N] - cums[r-1]
        d2 = abs(r2-s2)
        if d2 > d1: break
        r -= 1
        r1,s1,d1 = r2,s2,d2
    rs[l] = r1
    ss[l] = s1

ans = cums[-1] * 999
for p,q,r,s in zip(ps,qs,rs,ss):
    if p is None: continue
    tmp = max(p,q,r,s) - min(p,q,r,s)
    ans = min(ans, tmp)
print(ans)
### BUGGY CODE ###

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

def main():
    n , data = input_data()
    vMax = float('-inf')

    i = 1
    minIndex = min(enumerate(data) , key = lambda x:x[1])[0]
    for i, Ri in enumerate(data):
        if data[i+1:]:
            n = max(data[i+1:]) - Ri
            if vMax < n:
                vMax = n

        if i == minIndex: # Ri???????°???????????????¨????????????????¨??????????
            break

    print(vMax)

def input_data():
    n = int(input())
    lst = [int(input()) for i in range(n)]
    return (n , lst)

if __name__ == '__main__':
    main()

### FIXED CODE ###

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

def main():
    n , data = input_data()
    vMax = float('-inf')
    vMin = data.pop(0)

    for Rj in data:
        if vMax < Rj - vMin:
            vMax = Rj - vMin
        if vMin > Rj:
            vMin = Rj

    print(vMax)

def input_data():
    n = int(input())
    lst = [int(input()) for i in range(n)]
    return (n , lst)

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

n,m = map(int,input().split())
h_inputs = [int(i) for i in input().split()]
ab_inputs = [[int(j) for j in input().split()]for i in range(m)]

map_li = [[0 for i in range(n)] for i in range(n)]
ans = 0
for line in ab_inputs:
    a,b = line[0],line[1]
    map_li[a-1][b-1]=1
    map_li[b-1][a-1]=1

for i in range(n):
    tmp = 1
    for j in range(n):
        if map_li[i][j]==1:
            if h_inputs[i]<=h_inputs[j]:
                tmp=0
    if tmp==1:
        ans+=1
print(ans)


### FIXED CODE ###

n,m = map(int,input().split())
h_inputs = [int(i) for i in input().split()]
ab_inputs = [[int(j) for j in input().split()]for i in range(m)]

map_li = [1]*n
for line in ab_inputs:
    a,b = line[0],line[1]
    if h_inputs[a-1]>h_inputs[b-1]:
        map_li[b-1]=0
    if h_inputs[a-1]<h_inputs[b-1]:
        map_li[a-1]=0
    if h_inputs[a-1]==h_inputs[b-1]:
        map_li[a-1]=0
        map_li[b-1]=0
print(sum(map_li))
### BUGGY CODE ###

def InsertionSort(A, N, g):
    global cnt
    for i in range(g, N):
        key = A[i]
        j = i-g
        while j >= 0 and A[j] > key:
            A[j+g] = A[j]
            j = j-g
            cnt += 1    
        A[j+g] = key
    return A

def ShellSort(A, N):
    G = [len(A)//2]
    i = 0
    while True:
        if G[i] == 0 and len(G) == 1:
            G[i] = 1
            break
        if G[i]//2 == 0:
            break
        G.append(G[i]//2)
        i += 1
    

    for i in range(len(G)):
        InsertionSort(A, N, G[i])
    return G

N = int(input())
A = []
cnt = 0
for i in range(N):
    A.append(int(input()))
ShellSort(A,N)
print(len(ShellSort(A,N)))
print(*ShellSort(A,N))
print(cnt)
print(*A, sep='\n')

### FIXED CODE ###

import math
def InsertionSort(A, N, g):
    global cnt
    for i in range(g, N):
        key = A[i]
        j = i-g
        while j >= 0 and A[j] > key:
            A[j+g] = A[j]
            j = j-g
            cnt += 1    
        A[j+g] = key
    return A

def ShellSort(A, N):
    G = []
    i = 1
    while True:
        if  3**i -1 > N*2:
            break
        G.insert(0, int((3**i-1)/2))
        i += 1


    for i in range(len(G)):
        InsertionSort(A, N, G[i])
    return G

N = int(input())
A = []
cnt = 0
for i in range(N):
    A.append(int(input()))
ShellSort(A,N)
print(len(ShellSort(A,N)))
print(*ShellSort(A,N))
print(cnt)
print(*A, sep='\n')
### BUGGY CODE ###

import numpy as np

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

# インデックスはライフ 値はそれを以下にする最小MP
dp = [np.inf for i in range(H+1)]
dp[0] = 0

for i in range(1, H+1):
    quietus_MP = np.inf
    for a, b in AB:
        if i-a >= 0:
            dp[i] = min(dp[i-a]+b, dp[i])
        # 一回で倒せて一番MP使わない魔法
        if a > i:
            quietus_MP = min(b, quietus_MP)
    # 一回で倒す場合
    dp[i] = min(quietus_MP, dp[i])

print(dp[-1])

### FIXED CODE ###

import numpy as np

H, N = map(int, input().split())
AB = np.array([list(map(int, input().split())) for i in range(N)])
A = AB[:, 0]
B = AB[:, 1]

# インデックスはライフ 値はそれを以下にする最小MP
dp = np.array([10**10 for i in range(H+1)], dtype=int)
# dp = np.array([np.inf for i in range(H+1)], dtype=int)
dp[0] = 0

for i in range(1, H+1):
    # print(np.maximum(i-A, 0))
    dp[i] = min(dp[np.maximum(i-A, 0)] + B)

print(dp[-1])
### BUGGY CODE ###

import sys
import os
import itertools
from collections import deque

def main():
    if os.getenv("ENV")=='LOCAL':
        sys.stdin = open(os.path.dirname(__file__)+'/input.txt', 'r')

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

    ans=0
    for i in range(N):
        for j in range(N):
            if i != j and A[i]%A[j]==0:
                break
            elif j==N-1:
                ans+=1

    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
import os
import itertools
from collections import deque

def main():
    if os.getenv("ENV")=='LOCAL':
        sys.stdin = open(os.path.dirname(__file__)+'/input.txt', 'r')

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

    A.sort()
    ans=0
    # print(A)

    T=[True]*A[-1]
    # T[0]=False

    for i,a in enumerate(A):
        if T[a-1]:
            j=2*a
            while j <= A[-1]:
                T[j-1]=False
                j+=a
            if not i+1==len(A):
                if A[i]==A[i+1]:
                    T[a-1]=False

    for a in A:
        if T[a-1]:
            ans+=1

    print(ans)

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

# coding: utf-8
mod = 998244353
N, S = list(map(int, input().split()))
A = [0] + list(map(int, input().split()))

dp = [[0 for _ in range(S+1)] for i in range(N+1)]

for k in range(0, N):
  for s in range(1, S+1):
    dp[k+1][s] += (2 * dp[k][s] - dp[k-1][s]) % mod
    if (s + A[k+1]) <= S:
      dp[k+1][s+A[k+1]] += (dp[k][s] - dp[k-1][s]) % mod

  if A[k+1] <= S:
    dp[k+1][A[k+1]] += k+1

print(dp[N][S] % mod)

### FIXED CODE ###

# coding: utf-8
import numpy as np
N, S = list(map(int, input().split()))
A = [0]+list(map(int, input().split()))

dt = np.array([[0 for _ in range(S+1)] for x in range(N+1)])

for n in range(1, N+1):
  if A[n] <= S:
    dt[n,A[n]] += n
  if A[n] < S:
    dt[n, A[n]+1:] += dt[n-1,1:S-A[n]+1] - dt[n-2,1:S-A[n]+1]
  dt[n,:] += dt[n-1,:] * 2 - dt[n-2,:]
  dt[n,:] %= 998244353
print(dt[N,S] % 998244353)
### BUGGY CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
a=sorted(a,reverse=True)
b=sorted(b)

def ok(N):
    sums=0
    for i in range(n):
        sums+=max(0,a[i]-N//b[i])
    if sums<=k:
        return True
    else:
        return False
    
import math

left=0
right=a[0]*b[-1]
P=0
for i in range(41):
    if 2**i<=right<2**(i+1):
        P=i+1
        break

for _ in range(P):
    if ok(math.floor((left+right)/2)):
      left=left
      right=(left+right)/2
    elif not ok(math.floor((left+right)/2)):
      left=(left+right)/2
      right=right
print(math.floor(right))

### FIXED CODE ###

# いきぬきreview　忘れた問題
# gluttony
N, K = map(int, input().split())
A = list(map(int, input().split()))
F = list(map(int, input().split()))
F.sort()
A.sort(reverse=True)


def func(X):
    s = 0
    for i in range(N):
        a, f = A[i], F[i]
        s += max(0, a-X//f)
    return s <= K


R = 10**12
L = -1
while R-L > 1:
    m = (R+L)//2
    if func(m):
        R = m
    else:
        L = m
print(R)
### BUGGY CODE ###

n, k = map(int, input().split())
a = list(map(int, input().split()))
l = [1]
for i in range(n):
    if a[l[i] - 1] in l:
        res = l[:l.index(a[l[i] - 1])]
        cyc = l[l.index(a[l[i] - 1]):]
        break
    else:
        l += [a[l[i] - 1]]
print(cyc[(k - len(res)) % len(cyc)] if k > len(res) - 1 else res[k])

### FIXED CODE ###

n, k = map(int, input().split())
a = list(map(lambda x: int(x) - 1, input().split()))
visited = [-1 for _ in range(n)]
visited[0] = 0
l = [0]
for i in range(k):
    nex = a[l[i]]
    if visited[nex] != -1:
        res = visited[nex]
        cyc = i + 1 - visited[nex]
        break
    else:
        l += [nex]
        visited[nex] = i + 1
else:
    res = k + 1
print(l[res + (k - res) % cyc] + 1 if k > res else l[k] + 1)
### BUGGY CODE ###

import heapq

N, M = list(map(int, input().split()))
A = list(map(lambda x: -int(x), input().split()))

for i in range(M):
    heapq.heapify(A)
    _ = -heapq.heappop(A)
    _ = int(_ / 2)
    heapq.heappush(A, -_)

print(-sum(A))


### FIXED CODE ###

import heapq

N, M = list(map(int, input().split()))
A = list(map(lambda x: -int(x), input().split()))

heapq.heapify(A)

for i in range(M):
    _ = -heapq.heappop(A)
    _ = int(_ / 2)
    heapq.heappush(A, -_)

print(-sum(A))
### BUGGY CODE ###

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

from collections import Counter
AC=Counter(A)

for a in A:
    ACT=AC.copy()
    ACT[a]-=1
    print(int(sum(map(lambda x: x*(x-1)/2, ACT.values()))))

### FIXED CODE ###

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

from collections import Counter
AC=Counter(A)
ans=int(sum(map(lambda x: x*(x-1)/2, AC.values())))
for a in A:
    print(max(ans-AC[a]+1,0))
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
mod=10**9+7
ans=0
for i in range(61):
    count0=0
    count1=0
    for j in a:
        if not (j>>i & 1):
            count0+=1
        if j>>i & 1:
            count1+=1
    ans+=((count0*count1)*(2**i))%mod
    
print(ans%mod)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
mod=10**9+7
ans=0
k=1
for i in range(61):
    count0=0
    count1=0
    for j in a:
        if not (j>>i & 1):
            count0+=1
        if j>>i & 1:
            count1+=1
    ans+=((count0*count1)*(k))%mod
    k=(2*k)%mod
    
    
print(ans%mod)
### BUGGY CODE ###

X=int(input())

Xkon=X**0.2
if(Xkon==int(Xkon)):
    print(str(0)+" "+str(int(-Xkon)))
    #break
else:
    n=1
    while n<10**4:
        A=X+(n**5)
        check=(A**0.2)
        if(check==int(check)):
            AnsA=check
            AnsB=n
            print(str(int(AnsB)+" "+str(int(-AnsA))))
            break
        else:
            n=n+1
    m=-(10**4)
    while m<0:
        A=X+(m**5)
        check=(A**0.2)
        # print(type(check))
        if(type(check)!=complex):
            if(check==int(check)):
                AnsA=-check
                AnsB=-m
                print(str(int(AnsB))+" "+str(int(AnsA)))
                break
            else:
                pass
        else:
            m=m+1

### FIXED CODE ###

X=int(input())

for A in range(-1000,1000):
    for B in range (-1000,1000):
        if(A**5-B**5==X):
            print(A,B)
            break
    else:
        continue
    break
### BUGGY CODE ###

N=int(input())
for i in range(1,3501):
    for j in range(1,3501):
        if N*((i+j)/(i*j))/4==int(N*((i+j)/(i*j))/4):
            h=i
            n=j
            w=int(N*((i+j)/(i*j))/4)
            break
print(h,n,w)

### FIXED CODE ###

N=int(input())
for i in range(1,3501):
    for j in range(1,3501):
        bw=4*i*j-N*i-N*j
        if bw<=0:
            continue
        if (N*i*j)%bw==0:
            print(i,j,(N*i*j)//bw)
            exit()
### BUGGY CODE ###

import numpy as np

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

num_A = [A.count(i) for i in range(10**5+1)]
first = sum(np.array(num_A)*np.array([j for j in range(10**5+1)]))

for i in range(Q):
    b, c = map(int, input().split())
    first += c*num_A[b]
    first -= b*num_A[b]
    num_A[c] += num_A[b]
    num_A[b] = 0
    print(first)

### FIXED CODE ###

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

num_A = [0 for i in range(10**5+1)]
first = 0

for a in A:
    num_A[a] += 1
    first += a

for i in range(Q):
    b, c = map(int, input().split())
    first += c*num_A[b]
    first -= b*num_A[b]
    num_A[c] += num_A[b]
    num_A[b] = 0
    print(first)