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

MOD = 10**9+7

def add(a,b):
  return (a+b) % MOD

def sub(a,b):
  return (a-b) % MOD

def mul(a,b):
  return ((a%MOD) * (b%MOD)) % MOD

def pow(a,n):
  ans = 1
  mag = a
  for b in reversed(str(bin(n))):
    if b == 'b': break
    if b == '1':
      ans = mul(ans, mag)
    mag = mul(mag, mag)
  return ans

def inv(a):
  return pow(a, MOD-2)

factorical = [1]
factorical_inv = [1]
for n in range (1,200002):
  f = mul(factorical[-1], n)
  factorical.append(f)
  factorical_inv.append(inv(f))

def ncr(n,r):
  return mul(mul(factorical[n], factorical_inv[n-r]), factorical_inv[r])

H,W,A,B = map(int,raw_input().split())

def paths(w,h):
  return ncr(w+h,w)

ans = 0
for i in range(W-B):
  p = mul(paths(H-A-1, B+i), paths(A-1, W-B-1-i))
  ans = add(ans, p)
print ans

### FIXED CODE ###

MOD = 10**9+7

def add(a,b):
  return (a+b) % MOD

def mul(a,b):
  return (a*b) % MOD

def pow(a,n):
  ans = 1
  mag = a
  for b in reversed(str(bin(n))):
    if b == 'b': break
    if b == '1':
      ans = mul(ans, mag)
    mag = mul(mag, mag)
  return ans

def inv(a):
  return pow(a, MOD-2)

H,W,A,B = map(int,raw_input().split())

factorical = [1]
factorical_inv = [1]
for n in range (1,H+W+1):
  f = mul(factorical[n-1], n)
  factorical.append(f)
  if(n <= max(H,W)):
    factorical_inv.append(inv(f))

def ncr(n,r):
  return mul(mul(factorical[n], factorical_inv[n-r]), factorical_inv[r])

def paths(w,h):
  return ncr(w+h,w)

ans = 0
for i in range(W-B):
  p = mul(paths(H-A-1, B+i), paths(A-1, W-B-1-i))
  ans = add(ans, p)
print ans
### BUGGY CODE ###

n,m = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(m)]
ab.sort()
s = []
g = []
for a, b in ab:
    if a == 1: s.append(b)
    elif b == n: g.append(a)
ans = "IMPOSSIBLE"
if len(s) > 0 and len(g) > 0:
    if len(s) < len(g):
        for i in range(len(s)):
            if s[i] in g: ans = "POSSIBLE"
    else:
        for i in range(len(g)):
            if g[i] in s: ans = "POSSIBLE"
print(ans)

### FIXED CODE ###

n,m = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(m)]
ab.sort()
AB = sorted(ab, reverse=True, key=lambda x:x[1])
s = [0] * n
ans = "IMPOSSIBLE"
for a,b in ab:
    if a == 1: s[b-1] = 1
    else: break
for A, B in AB:
    if B == n:
        if s[A-1] == 1:
            ans = "POSSIBLE"
    else: break
print(ans)
### BUGGY CODE ###

A, B, C, K = map(int, input().split())
cards = [1 for _ in range(A)]
cards += [0 for _ in range(B)]
cards += [-1 for _ in range(C)]
print(sum(cards[:K]))

### FIXED CODE ###

A, B, C, K = map(int, input().split())
ans = 0
if K >= A+B:
    ans = A - (K-A-B)
else:
    ans = K
print(ans)
### BUGGY CODE ###

x = int(input())
tmp = 0

for i in range(x,10**111):
  for j in range(2,(i//2)+2):
    tmp += 1
    if i%j == 0:
      break
    elif tmp == (i//2):
      print(i)
      exit()
      

### FIXED CODE ###

x = int(input())
tmp = 0

if x == 2:
  print(2)
  exit()
for i in range(x,10**111):
  for j in range(2,(i//2)+2):
    tmp += 1
    if i%j == 0:
      break
    elif tmp == (i//2):
      print(i)
      exit()
### BUGGY CODE ###

N,K=map(int,input().split())
A=list(map(int,input().split()))
TOWN=[i for i in range(1,N+1)]

#行ったことある町リスト
d=[1]
i=0
for i in range(K):
  T=A[d[-1]-1]
  if T in d:
    break
  d.append(T)
F=d.index(T)
LOOP_TOWN=d[F:]
q=(K-F)%len(LOOP_TOWN)
print(LOOP_TOWN[q])

### FIXED CODE ###

def main():
  N,K=map(int,input().split())
  A=list(map(int,input().split()))
  n=[0]*N
  #行ったことある町リスト
  d=[1]
  for _ in range(K):
    T=A[d[-1]-1]
    if n[T-1]==1:
      break
    else:
      n[T-1]=1
    d.append(T)
  F=d.index(T)
  LOOP_TOWN=d[F:]
  q=(K-F)%len(LOOP_TOWN)
  print(LOOP_TOWN[q])

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


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

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

for i in range(M):
    A = sorted(A, reverse=True)
    A[0] = int(A[0] / 2)
    
from functools import reduce

print(reduce(lambda x, y:x + y, A))


### FIXED CODE ###

from heapq import heapify, heappop, heappush

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

heapify(A)
for i in range(M):
    heappush(A, int(heappop(A) / 2))

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

from collections import defaultdict,deque
import copy
import numpy as np
import bisect

N = int(input())
A = list(map(int,input().split()))
graph = defaultdict(deque)
for _ in range(0,N-1):
    u,v = map(int,input().split())
    graph[u].append(v)
    graph[v].append(u)

arrive = [False] * (N+1)
dp_dict = np.array([None]*N)
dp_dict[0] = [A[0]]


ans = [None] *(N+1)
def dfs(s):
    stack = deque([s])
    while stack:
        v = stack[-1]
        arrive[v] = True
        if graph[v]:
            w = graph[v].pop()
            if arrive[w] == False:
                tar = A[w-1]
                dp = dp_dict[v-1][:]
                if tar > dp[-1]:
                    dp.append(tar)
                else:
                    dp[bisect.bisect_left(dp, tar)] = tar
                ans[w] = len(dp)
                dp_dict[w-1] = dp
                stack.append(w)

        else:
            stack.pop()


dfs(1)
ans[1] = 1
for i in ans[1::]:
    print(i)

### FIXED CODE ###

import bisect
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)
 
N = int(input())
A = tuple(map(int, input().split()))
graph = [[] for _ in range(N + 1)]
for _ in range(N - 1):
    x, y = map(int, input().split())
    graph[x].append(y)
    graph[y].append(x)
 
ans = [-1] * (N + 1)
inf = 10**18
LIS = [inf] * (N + 1)
 
def DFS(s, parent=0):
    a = A[s - 1]
    i = bisect.bisect_left(LIS, a)
    v = LIS[i]
    LIS[i] = a
    ans[s] = bisect.bisect_left(LIS, inf)
    for t in graph[s]:
        if t == parent:
            continue
        DFS(t, s)
    LIS[i] = v
    return
 
DFS(1)
print(*ans[1:], sep="\n")
### BUGGY CODE ###

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

m=max(A)

for i in range(1,m+1):
    print(A.count(i))

for j in range(m+1,N+1):
    print(0)



### FIXED CODE ###


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

A.sort()
if A[0]==0:
    A.remove(0)

l=len(A)
k=0

ans=1

m=max(A)

for i in range(l-1):
    if A[i+1]>A[i]:
        k=A[i]
        print(ans)
        while A[i+1]!=k+1:
            k=k+1
            print(0)
        ans=1
    else:
        ans=ans+1
if A[l-1]==A[l-2]:
    print(ans)
else:
    print(ans)
    
   
for j in range(m+1,N+1):
    print(0)
### BUGGY CODE ###

import math

A, B, N = map(int, input().split(' '))

_max = 0
for x in range(N, int(N/2), -1):
    if x < 1:
        break
    num =math.floor(A * x / B) - A * math.floor(x/B) 
    # print(num)
    if  num > _max:
        _max = num

print(_max)


### FIXED CODE ###

import math

def floor(A, B, x):
    return math.floor(A * x / B) - A * math.floor(x/B) 

A, B, N = map(int, input().split(' '))
x = min(N, B-1)
print(floor(A,B,x))
### BUGGY CODE ###

#n=list(map(int,input().split()))
n = int(input()) #1行目のNを取得する
num = [input() for i in range(n)] #複数行の数値の入力を取得
    
for i in range(n):
    print(max(num[:i]+num[i+1:]))

### FIXED CODE ###

import sys
input = sys.stdin.readline
import numpy as np
n = int(input()) 
num = [input() for _ in range(n)] 
num = np.array(num).astype("int64")
#ma=max(num)
#ind=num.index(ma)
sorted_num=sorted(num)
ma=sorted_num[-1]
ma2=sorted_num[-2]
for i in range(n):
    if ma != num[i]:
        print(str(ma).strip())
    else:
        print(str(ma2).strip())
### BUGGY CODE ###

import sys
read = sys.stdin.readline
import time
from heapq import heappush, heappop, heapify
import math
import itertools as it
from collections import deque 


def inp():
    return int(input())
def inpl():
    return list(map(int, input().split()))
start_time = time.perf_counter()
# ------------------------------

mod = 10**9 + 7

N = inp()
A = inpl()
wa = 0
for i in range(0, N - 1):
    for j in range(i+1, N):
        wa = (wa + A[i] * A[j]) % mod
print(wa)

# -----------------------------
end_time = time.perf_counter()
print('time:', end_time-start_time, file=sys.stderr)



### FIXED CODE ###

import sys
read = sys.stdin.readline
import time
from heapq import heappush, heappop, heapify
import math
import itertools as it
from collections import deque 


def inp():
    return int(input())
def inpl():
    return list(map(int, input().split()))
start_time = time.perf_counter()
# ------------------------------


mod = 10**9 + 7

N = inp()
A = inpl()
wa = 0
sm = A[0]
for i in range(1, N):
    wa = (wa + sm * A[i]) % mod
    sm = (sm + A[i]) % mod
print(wa)

# -----------------------------
end_time = time.perf_counter()
print('time:', end_time-start_time, file=sys.stderr)
### BUGGY CODE ###

number =int(input())
orders =input().rstrip().split(" ")
for j in range(number):
  for i in range(len(orders)):
    if int(orders[i])==j+1:
    	print(i+1 ,end=" ")

### FIXED CODE ###

n=int(input())
numbers=input().rstrip().split(" ")
order=[0 for i in range(n)]
for (i,number) in enumerate(numbers):
    order[int(number)-1]=i+1
#print(order)
for num in order:
    print(num,end=" ")
### BUGGY CODE ###

def main():
    [N, M] = [int(number) for number in input().split()]
    part_times = []
    for i in range(N):
        job= [int(number) for number in input().split()]
        part_times.append(job)
    part_times = [part_time for part_time in sorted(part_times, key = lambda x: (x[1], x[0]), reverse=True)] #if part_time[0] <= M]
    money = 0
    #day = 0
    #earns = []
    for day in range(M):
        for part_time in part_times:
            if part_time[0] <= day + 1:
                money += part_time[1]
                part_times.remove(part_time)
                break
        """
        try:
            todays_part = next(itertools.ifilter(lambda x: x[0] <= day+1, part_times), None)
            money += todays_part[1]
            part_times.remove(todays_part)
        except:
            continue
        """

    """
    for [income_day, earn] in part_times:
        remain_day = M - day
        if remain_day >= income_day:
            money += earn
        else:
            min_earn = min(earns)
            if earn > min_earn:
                money += earn
                money -= min_earn
                earns.remove(min_earn)
        earns.append(earn)
        day += 1
    """
    print(money)

if __name__ == '__main__':
    main()


### FIXED CODE ###

import heapq

def main():
    [N, M] = [int(number) for number in input().split()]
    part_times = []
    for i in range(N):
        job= [int(number) for number in input().split()]
        part_times.append(job)
    part_times = [part_time for part_time in sorted(part_times, key = lambda x: x[0])] #if part_time[0] <= M]
    money = 0
    hp = []
    for day in range(M):
        while part_times != [] and part_times[0][0] <= day + 1:
            part_time = part_times[0]
            heapq.heappush(hp, - part_time[1])
            part_times.pop(0)
        if hp != []:
            money -= heapq.heappop(hp)

    print(money)

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

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

for i in range(1,1+N):
    print(A.count(i))

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
D = [0 for i in range(N)]

for i in A:
    D[i-1] += 1

for i in range(len(D)):
    print(D[i])
### BUGGY CODE ###

x = int(input())
ans = 0
for i in range(1,1000):
    for j in range(2,1000):
        if i ** j <= x:
            ans = max(ans,i ** j)
print(ans)

### FIXED CODE ###

x = int(input())
k = 0

for i in range(1,1000):
    for j in range(2,1000):
        if i ** j <= x:
            k = max(k,i ** j)
        else:
            break
    if x // 2 < i:
        break

print(k)
### BUGGY CODE ###

m = 2019
div_list = [0]*m
div_list[0] += 1
S = list(input())
num = 0
for i, l in enumerate(reversed(S)):
    num += 10**i*int(l)
    div_list[num%m] += 1

ans = 0
for item in div_list:
    ans += int(item*(item-1)/2)

print(ans)


### FIXED CODE ###

from sys import stdin
input = stdin.readline

def main():
    S = list(input())
    S.pop()
    m = 2019
    div_list = [0]*m
    num = 0
    for i, l in enumerate(reversed(S)):
        num += pow(10, i, m)*int(l)
        div_list[num%m] += 1

    div_list[0] += 1
    ans = 0
    for item in div_list:
        ans += int(item*(item-1)/2)

    print(ans)

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

import numpy as np
n,m=map(int,input().split())
a=sorted([int(i) for i in input().split()])
h=[]
for i in range(m):
    h.append([int(i) for i in input().split()])
h.sort(key=lambda x: x[1], reverse=True)
for j in h:
    k=np.sum(a[i]<j[1] for i in range(n))
    if k==0:
        break
    for g in range(min(k,j[0])):
        a[g]=j[1]
    a.sort()
print(sum(a))

### FIXED CODE ###

n,m=map(int,input().split())
a=sorted([int(i) for i in input().split()])
bc=[list(map(int,input().split())) for _ in range(m)]
bc=sorted(bc,key=lambda x : x[1],reverse=True)
min_a=min(a)
count=0
for b,c in bc:
    if min_a >=c and count>=n:
        break
    else:
        l=min(b,n-count)
        for i in range(l):
            count+=1
            a.append(c)
a.sort()
print(sum(a[count:]))
### BUGGY CODE ###

def cal(n,s):
	val = [-1]*n
	for i in range(n):
		val[i] = sum(s[:i] == 'W') + sum(s[i+1:] == 'E')
	return min(val)

import numpy as np
n = int(input())
s = np.array(list(input()))
print(cal(n,s))

### FIXED CODE ###

def cal(n,s):
	cum = np.cumsum(s == 'W')
	val = [-1]*n
	for i in range(n):
		W = cum[i-1]  if i-1 >= 0 else 0 #i <- W
		H = (n-i-1) - (cum[-1] - cum[i])	 #i -> H 
		val[i] = W+H
	return min(val)

import numpy as np

n = int(input())
s = np.array(list(input()))
print(cal(n,s))
### BUGGY CODE ###

a, b, k = map(int,input().split())

for i in range(a, b+1):
    if  i <= a+k-1 or b+1-k <= i:
        print(i)

### FIXED CODE ###

a, b, k = map(int,input().split())
if a+k+1 <= b:
    for i in range(a, k+a):
        print(i)
    if a+k+1 <= b+1-k:
        for i in range(b+1-k, b+1):
            print(i)
    else:
        for i in range(a+k, b+1):
            print(i)
else:
    for i in range(a, b+1):
        print(i)
### BUGGY CODE ###

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

def main(N,M,islands):
    queue = []
    flag = False
    for a,b in islands:
        if(a==1):
            queue.append(b)
    for a,b in islands:
        if(a in queue and b==N):
            flag = True
            break
            
    print("POSSIBLE") if flag else print("IMPOSSIBLE")

if __name__ == '__main__':
    N, M = map(int, input().split())
    islands = []
    for i in range(M):
        a, b = map(int, input().split())
        if(a==1 or b==N):
            islands.append([a,b])
    main(N,M,islands)

### FIXED CODE ###

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

def main(N,M,visited,queue):
    ans = "IMPOSSIBLE"

    for i in queue:
        if visited[i-1] == True:
            ans = "POSSIBLE"
            break
            
    print(ans)

if __name__ == '__main__':
    N, M = map(int, input().split())
    visited,queue = [False]*N, []
    for i in range(M):
        a, b = map(int, input().split())
        if(a==1):
            visited[b-1] = True
        elif(b==N):
            queue.append(a)
    main(N,M,visited,queue)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
N, K = map(int, input().split())
A_list = list(map(int, input().split()))

ans_list = [1]
before_town = 1
loop_start_town = 10 ** 10
for i in range(N):
    now_town = A_list[before_town - 1]
    ans_list.append(now_town)
    before_town = now_town

if N >= K:
    print(ans_list[K])
else:
    ans_list = sorted(set(ans_list), key = ans_list.index)
    loop_start_idx = ans_list.index(A_list[ans_list[-1] - 1])
    loop_len = len(ans_list)
    ans_list = ans_list[loop_start_idx:]
    mod_num = (K - loop_len) % (loop_len - loop_start_idx)
    print(ans_list[mod_num])

### FIXED CODE ###

# -*- coding: utf-8 -*-
N, K = map(int, input().split())
A_list = list(map(int, input().split()))

ans_list = [1]
history_list = [0 for _ in range(N)]
before_town = 1
loop_start_town = 10 ** 10
for i in range(N):
    now_town = A_list[before_town - 1]
    if history_list[now_town - 1] == 1:
        break
    ans_list.append(now_town)
    before_town = now_town

if len(ans_list) > K:
    print(ans_list[K])
else:
    loop_start_idx = ans_list.index(A_list[ans_list[-1] - 1])
    loop_len = len(ans_list)
    ans_list = ans_list[loop_start_idx:]
    mod_num = (K - loop_len) % (loop_len - loop_start_idx)
    print(ans_list[mod_num])
### BUGGY CODE ###

import sys
N, K = map(int, input().split())
first = N
list_a = []

if K == 1:
    print(0)
    sys.exit()
else:
    while N > 0:
        N = N - K

second = N + K

N = abs(N)

list_a.append(N)
list_a.append(second)
list_a.append(first)

list_a = sorted(list_a)

print(list_a[0])


### FIXED CODE ###

import sys
N, K = map(int, input().split())
first = N
list_a = []

if N % K == 0:
    print(0)
    sys.exit()
else:
    X = N // K
    N = N - (K * (X+1))

second = N + K

N = abs(N)

list_a.append(N)
list_a.append(second)
list_a.append(first)

list_a = sorted(list_a)

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

import sys
input = sys.stdin.readline

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

for i in range(Q):
    a,b=map(int,input().split())
    print(S[a-1:b].count("AC"))

    


### FIXED CODE ###

import sys

input=sys.stdin.readline

N,Q=map(int,input().split())
S=input()
A=[]
B=[]
l=[0]

for _ in range(Q):
    a,b=map(int,input().split())
    A.append(a)
    B.append(b)

count=0
for i in range(1,N):
    if S[i-1]=="A" and S[i]=="C":
        count+=1
    l.append(count)

for i in range(Q):
    print(l[B[i]-1]-l[A[i]-1])
### BUGGY CODE ###

h,w=list(map(int,input().split()))
m=[]
for i in range(h):
  mm=[]
  for j in input():
    mm.append(1 if j=="#" else 0)
  m.append(mm)

wl=[[0 for i in range(w)]for j in range(h)]
for i in range(h):
  s=0
  t=0
  while t<w:
    while t<w and m[i][t]==0:
      t+=1
    for j in range(s,t):
      wl[i][j]=t-s
    s=t+1
    t=t+1
mx=0
for i in range(w):
  s=0
  t=0
  while t<h:
    while t<h and m[t][i]==0:
      t+=1
    for j in range(s,t):
      k=wl[j][i]
      if mx<k+t-s:
        mx=k+t-s
    s=t+1
    t=t+1


print(mx-1)

### FIXED CODE ###

h,w=list(map(int,input().split()))
m=[]
for i in range(h):
  mm=[]
  for j in input():
    mm.append(1 if j=="#" else 0)
  m.append(mm)

wl=[[0 for i in range(w)]for j in range(h)]
for i in range(h):
  s=0
  t=0
  while t<w:
    while t<w and m[i][t]==0:
      t+=1
    for j in range(s,t):
      wl[i][j]=t-s
    s=t+1
    t=t+1
mx=0
for i in range(w):
  s=0
  t=0
  while t<h:
    while t<h and m[t][i]==0:
      t+=1
    for j in range(s,t):
      k=wl[j][i]
      if mx<k+t-s:
        mx=k+t-s
    s=t+1
    t=t+1


print(mx-1)
### BUGGY CODE ###

#import sys

#input = sys.stdin.readline



def main():
#    h,w,a,b = map(int, input().split())
    n=int(input())
    l=list(map(int,input().split()))
    l=sorted(l,reverse=True)
    count=0
    for i in range(n-2):
        for j in range(i+1,n-1):
            for m in range(j+1,n):
                if l[m]>abs(l[i]-l[j]):
                    count+=1
                else:
                    break

    print(count)






if __name__ == "__main__":
    main()

### FIXED CODE ###

#import sys

#input = sys.stdin.readline

import bisect

def main():
#    h,w,a,b = map(int, input().split())
    n=int(input())
    l=list(map(int,input().split()))
    l=sorted(l)
 #   print(l)
    count=0
    for i in range(n-2):
        for j in range(i+1,n-1):
            a = bisect.bisect_left(l,l[i]+l[j])
#            print(a)
            count+=a-j-1

    print(count)






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

import numpy as np

n = int(input())
abc_list = [[int(i) for i in input().split()] for j in range(n)]
abc_list = np.array(abc_list)

dp = np.zeros((n, 3))
dp[0,:] = abc_list[0,:]

temp_indexes = np.array([0, 1, 2])
for i in range(1, n):
    for j in range(3):
        indexes = temp_indexes[temp_indexes!=j]
        bigger = max(dp[i-1][indexes[0]], dp[i-1][indexes[1]])
        dp[i][j] = bigger + abc_list[i][j]
        
print(int(np.max(dp[-1,:])))

### FIXED CODE ###

n = int(input())
abc_list = [[int(i) for i in input().split()] for _ in range(n)]

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


for i, abc in enumerate(abc_list):
    for j in range(3):
        temp = dp[i][:]
        temp.pop(j)
        dp[i+1][j] = max(temp) + abc[j]

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

def main():
    s = input()
    r = 0
    lens = len(s)
    for i1 in range(lens - 3):
        tnum = sum(list(map(int, s[i1:i1 + 4])))
        tint = int(s[i1:i1+4])
        if tnum % 3 == 0:
            r += tint % 673 == 0
        for i2 in range(i1+4,lens):            
            es = int(s[i2])
            tnum += es
            tint = tint*10 + es
            if tnum % 3 == 0:
                r += tint % 673 == 0
    print(r)

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
from collections import Counter
def main():
    s = input()
    n = len(s)

    amari = [0] * n
    ketaamari = 1
    t = 0
    for i1 in range(n):
        t = (t + ketaamari * int(s[-i1 -1])) % 2019
        amari[-i1-1] = t
        ketaamari = (ketaamari * 10) % 2019
    amari.append(0)
    ac = Counter(amari)
    r = 0
    for v in ac.values():
        r += v * (v - 1) // 2
    print(r)

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


def main():
    n = int(input())
    a = list(map(int, input().split(" ")))
    q = int(input())
    bc = []
    for _ in range(q):
        bc.append(list(map(int, input().split(" "))))
    for i in range(q):
        for j in range(n):
            if bc[i][0] == a[j]:
                a[j] = bc[i][1]
        print(sum(a))
        
    


if __name__ == "__main__":
    main()

### FIXED CODE ###

from collections import defaultdict
def main():
    n = int(input())
    a = list(map(int, input().split(" ")))
    q = int(input())
    bc = []
    sum1 = sum(a)
    for _ in range(q):
        bc.append(list(map(int, input().split(" "))))
    d = defaultdict(lambda:0)
    for i in range(n):
        d[a[i]] += 1

    for i in range(q):
        if bc[i][0] in d:
            sum1 += (bc[i][1] - bc[i][0]) * d[bc[i][0]]
            d[bc[i][1]] += d[bc[i][0]]
            del d[bc[i][0]] 
        print(sum1)
        

if __name__ == "__main__":
    main()