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

import sys
import math
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid(h, w, num): return [[int(num)] * w for _ in range(h)]


#隣接リスト 1-order
def make_adjlist_d(n, edges):
    res = [[] for _ in range(n + 1)]
    for edge in edges:
        res[edge[0]].append(edge[1])
        res[edge[1]].append(edge[0])
    return res


def make_adjlist_nond(n, edges):
    res = [[] for _ in range(n + 1)]
    for edge in edges:
        res[edge[0]].append(edge[1])
    return res


#nCr
def cmb(n, r):
    return math.factorial(n) // math.factorial(r) // math.factorial(n - r)


def main():
    N = NI()
    A = NLI()
    A = sorted(A)

    hurui = [1] * len(A)
    prev = 0
    for i, a in enumerate(A):
        if a == prev:
            hurui[i-1] = 0
            hurui[i] = 0
            prev = a
            continue
        if i == len(A)-1:
            prev = a
            continue
        if hurui[i] == 0:
            prev = a
            continue
        for j, b in enumerate(A[i+1:]):
            if hurui[i+1+j]==0:
                prev = a
                continue
            if b % a == 0:
                hurui[i+1+j] = 0
            prev = a
    print(sum(hurui))



if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
import math
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid(h, w, num): return [[int(num)] * w for _ in range(h)]


#隣接リスト 1-order
def make_adjlist_d(n, edges):
    res = [[] for _ in range(n + 1)]
    for edge in edges:
        res[edge[0]].append(edge[1])
        res[edge[1]].append(edge[0])
    return res


def make_adjlist_nond(n, edges):
    res = [[] for _ in range(n + 1)]
    for edge in edges:
        res[edge[0]].append(edge[1])
    return res


#nCr
def cmb(n, r):
    return math.factorial(n) // math.factorial(r) // math.factorial(n - r)


def main():
    N = NI()
    A = NLI()
    A = sorted(A)

    ma = A[-1]
    hurui = [0] * (ma + 10)
    for a in A:
        if hurui[a] == 0:
            hurui[a] = 1
        else:
            hurui[a] = 10

    for a in A:
        if hurui[a] == 0:
            continue

        for i in range(a*2, ma+10, a):
            hurui[i] = 0

    print(hurui.count(1))



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

import sys 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N,M = map(int,readline().split())
WA_cnt = [0]*(N+1)
A = []
cnt = 0
for _ in range(M):
    p,S = readline().decode().split()
    p = int(p)
    if S == 'AC' and (p in A) == False:
        A.append(p) 
        cnt += WA_cnt[p]
    else:
        WA_cnt[p] += 1
        
print(len(set(A)),cnt)

### FIXED CODE ###

import sys 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N,M = map(int,readline().split())
WA_cnt = [0]*(N+1)
WA_use = [0]*(N+1)
A = []
cnt = 0
for _ in range(M):
    p,S = readline().decode().split()
    p = int(p)
    if S == 'AC' and WA_use[p] == 0:
        A.append(p) 
        cnt += WA_cnt[p]
        WA_use[p] = 1
    else:
        WA_cnt[p] += 1
        
print(len(set(A)),cnt)
### BUGGY CODE ###

N = int(input())
S = input()
from itertools import permutations
r = []
g = []
b = []
for i, s in enumerate(S):
    if s == 'R':
        r.append(i)
    elif s == 'G':
        g.append(i)
    else:
        b.append(i)

ans = len(r)*len(g)*len(b)

for A, B, C in permutations([r,g,b]):
    for i in A:
        for j in B:
            k = 2 * j - i
            if k < N and i < j < k and S[i] != S[j] and S[i] != S[k] and S[j] != S[k]: 
                ans -= 1
print(ans)

### FIXED CODE ###

N = int(input())
S = input()
from itertools import permutations
r = []
g = []
b = []
for i, s in enumerate(S):
    if s == 'R':
        r.append(i)
    elif s == 'G':
        g.append(i)
    else:
        b.append(i)

ans = len(r)*len(g)*len(b)

for A, B, C in permutations([r,g,b]):
    for i in A:
        for j in B:
            k = 2 * j - i
            if k < N and i < j < k and S[i] != S[j] and S[i] != S[k] and S[j] != S[k]: 
                ans -= 1
print(ans)
### BUGGY CODE ###

import heapq
import itertools
n,m,R=map(int,input().split())
r=list(map(int,input().split()))
edges=[[] for _ in range(n)]
for _ in range(m):
    a,b,c = map(int, input().split())
    a,b=a-1,b-1
    edges[a].append((b, c))
    edges[b].append((a, c))

def dijkstra(x,route):
    d=[float('inf')]*n
    d[x]=0
    visited={x}
    hq=[(0,x)]
    while hq:
        u=heapq.heappop(hq)[1]
        visited.add(u)
        for node, cost in route[u]:
            if (node not in visited) and d[node]>d[u]+cost:
                d[node]=d[u]+cost
                heapq.heappush(hq,(d[node],node))
    return d
dist=[[0 for _ in range(n)] for _ in range(n)]
for i in range(n):
    dist[i]=dijkstra(i,edges)
ans=float("inf")
t=itertools.permutations(r)
for i in t:
    d=0
    start=i[0]-1
    for end in i[1:]:
        d+=dist[start][end-1]
        start=end-1
    ans=min(ans,d)
print(ans)

### FIXED CODE ###

import heapq
import itertools
n,m,R=map(int,input().split())
r=list(map(int,input().split()))
edges=[[] for _ in range(n)]
for _ in range(m):
    a,b,c = map(int, input().split())
    a,b=a-1,b-1
    edges[a].append((b, c))
    edges[b].append((a, c))

def dijkstra(x,route):
    d=[float('inf')]*n
    d[x]=0
    visited={x}
    hq=[(0,x)]
    while hq:
        u=heapq.heappop(hq)[1]
        visited.add(u)
        for node, cost in route[u]:
            if (node not in visited) and d[node]>d[u]+cost:
                d[node]=d[u]+cost
                heapq.heappush(hq,(d[node],node))
    return d
dist=[[] for _ in range(R)]
for i in range(R):
    start=r[i]-1
    dist[i]=dijkstra(start,edges)
ans=float("inf")
t=itertools.permutations(r)
for i in t:
    d=0
    start=i[0]
    for end in i[1:]:
        d+=dist[r.index(start)][end-1]
        start=end
    ans=min(ans,d)
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10000000)
n, q = map(int, input().split())

counter = [0 for _ in range(n+1)]
o = [0 for _ in range(n+1)]
g = [[] for _ in range(n+1)]

for i in range(n-1):
  a,b= map(int, input().split())
  g[a].append(b)
  g[b].append(a)

for i in range(q):
  p,x= map(int, input().split())
  o[p] += x


def dfs(p, parent):
  counter[p] += o[p] + counter[parent]
  for i in g[p]:
    if i != parent:
      dfs(i, p)
 
dfs(1, 0)
print(*counter[1:])

### FIXED CODE ###


n, q = map(int, input().split())

ct = [0] * (n+1)
o = [0] * (n+1)
g = [[] for _ in range(n+1)]

for i in range(n-1):
  a,b= map(int, input().split())
  g[a].append(b)
  g[b].append(a)

for i in range(q):
  p,x= map(int, input().split())
  o[p] += x

todo = [1]
seen = [False] * (n+1)
while todo:
  p = todo.pop(-1)
  ct[p] += o[p]
  seen[p] = True
  for i in g[p]:
    if seen[i]:
      ct[p] += ct[i]
    else:
      todo.append(i)

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

import sys
input = sys.stdin.readline

def main():
    n, m = map(int, input().split())
    lst = [[] for _ in range(n + 1)]
    py = []
    for i in range(m):
        p, y = map(int, input().split())
        py.append([p, y])
        lst[p].append(y)

    for i in range(n+1):
        lst[i] = sorted(lst[i])
    ans = []
    for i, j in py:
        ans.append(str(i).zfill(6) + str(lst[i].index(j)+1).zfill(6))
    print(*ans, sep=('\n'))

if __name__ == '__main__':
    main()

### FIXED CODE ###

n, m = map(int, input().split())
lst = [[] for _ in range(n + 1)]
py = [tuple(map(int, input().split())) for i in range(m)]

for i, (p, y) in enumerate(py):
    lst[p].append((y, i))

ans = [None] * m

for p, l in enumerate(lst):
    l.sort()
    for j, (y, i) in enumerate(l):
        ans[i] = str(p).zfill(6) + str(j + 1).zfill(6)

print(*ans, sep=('\n'))
### BUGGY CODE ###

import numpy as np

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

# [活発度, もとの番号] のリストを降順に並べる
A_list = [[A, index] for index, A in enumerate(A_list)]
A_list.sort(reverse=True)

# print(A_list)

dp = np.zeros((N+1, N+1), int)
# print(dp)

# right = 0
for left in range(N):
    activity = A_list[left][0]
    distance_from_left = abs(left - A_list[left][1])
    dp[left + 1][0] = dp[left][0] + activity * distance_from_left

# left = 0
for right in range(N):
    activity = A_list[right][0]
    distance_from_right = abs(N - 1 - right - A_list[right][1])
    dp[0][right + 1] = dp[0][right] + activity * distance_from_right

for left in range(1, N + 1):
    for right in range(1, N - left + 1):
        activity = A_list[left + right - 1][0]
        distance_from_left = abs((left - 1) - A_list[left + right - 1][1])
        distance_from_right = abs((N - right) - A_list[left + right - 1][1])
        score_if_appended_to_left\
            = dp[left - 1][right] + activity * distance_from_left
        score_if_appended_to_right\
            = dp[left][right - 1] + activity * distance_from_right
        dp[left][right] = max(score_if_appended_to_left,
                              score_if_appended_to_right)
        # print(dp)
print(np.max(dp))


### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
table = []
 
for i, a in enumerate(A):
    table.append([a,i])
table.sort()
 
# DP[i][j] 左端に i 個, 右端に j 個貪欲に詰めたときのうれしさ
DP = [[0 for i in range(N+1)] for j in range(N+1)]
for i in range(1,N+1):
    # i 人目 table[i-1] の幼児を移動させる
    baby, pos = table.pop()
    
    DP[i][0] = DP[i-1][0] + baby * abs(pos-i+1)
    DP[0][i] = DP[0][i-1] + baby * abs(pos-(N-i))
    for x in range(1,i):
        y = i - x
 
        #左端に置く場合と右端に置く場合でmax
        DP[x][y] = max(DP[x-1][y] + baby * abs(pos-x+1),\
                     DP[x][y-1] + baby * abs(pos-(N-y)))
 
ans = 0
for i in range(N+1):
    ans = max(ans, DP[i][N-i])
print(ans)
### BUGGY CODE ###

import copy
N=int(input())
li = list(map(int,input().split()))

for i in range(0,N):
	li[i] = li[i] - i -1
a = []
d = copy.copy(li)
while len(d) >= 3:
	d.remove(max(d))
	d.remove(min(d))
for i in range(min(d),max(d)+1):
	k = 0
	for j in range(N):
		k = k + abs(li[j]-i)
	a.append(k)
print(min(a))

### FIXED CODE ###

n = int(input())
a = [int(i) for i in input().split()]
for i in range(0,len(a)):
    a[i] -= (i+1)
a.sort()
b = [ abs(x  - (a[n//2])) for x in a]
print(sum(b))
### BUGGY CODE ###

from math import factorial
def comb(n,r):
  return factorial(n)//factorial(n-r)//factorial(r)
S=input()
N=len(S)
mod=[0 for i in range(2019)]
s=0
for i in range(1,N+1): 
  s+=int(S[-i])*(10**(i-1))
  mod2=s%2019
  mod[mod2]+=1
ans=0
for i in range(2019):
  k=mod[i]
  if i==0:
    if k>=2:
      ans+=comb(k,2)+k
    else:
      ans+=k
  else:
    if k>=2:
      ans+=comb(k,2)
print(ans)      

### FIXED CODE ###

import numpy as np
S=input()
N=len(S)
mod=[0 for i in range(2019)]
mod2=0
ten=1
for i in range(N-1,-1,-1): 
  s=int(S[i])*ten
  mod2+=np.mod(s,2019)
  mod2=np.mod(mod2,2019)
  mod[mod2]+=1
  ten=(ten*10)%2019
ans=0
for i in range(2019):
  k=mod[i]
  if i==0:
    if k>=2:
      ans+=k*(k-1)//2+k
    else:
      ans+=k
  else:
    if k>=2:
      ans+=k*(k-1)//2
print(ans)
### BUGGY CODE ###

A,B,K=map(int,input().split())
i=0
for i in range(K):
  if A>0:
    A-=1
  else:
    B-=1

print('{} {}'.format(A,B))

### FIXED CODE ###

A,B,K=map(int,input().split())

if A>=K:
  A=A-K
elif A+B<=K:
  A=B=0
else:
  B=A+B-K
  A=0

print('{} {}'.format(A,B))
### BUGGY CODE ###

n, m = map(int, input().split())
a = list(map(int, input().split()))

for _ in range(m):
    a[a.index(max(a))] = a[a.index(max(a))] // 2

print(sum(a))


### FIXED CODE ###

import heapq

n, m = map(int, input().split())
a = []
for i in list(map(int, input().split())):
    heapq.heappush(a, -i)

for _ in range(m):
    p = heapq.heappop(a)
    heapq.heappush(a, int(p/2))

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

import re
s = input()
res = re.finditer(r"(A*(BC)+)+", s)

def count(string):
    cnt = 0
    ind = len(string) - 1
    res = 0
    while ind >= 0:
        s = string[ind]
        if s == "C":
            ind -= 2
            cnt += 1
        else:
            ind -= 1
            res += cnt
    return res

ans = 0
for r in res:
    ans += count(r.group())
print(ans)


### FIXED CODE ###

s = input()
ind = 0
len_s = len(s)
string = ""
cnt = 0
ans = 0
while ind < len_s:
    _s = s[ind]
    if _s == "A":
        cnt += 1
        ind += 1
    elif _s == "B" and ind + 1 < len_s and s[ind + 1] == "C":
        ind += 2
        ans += cnt
    else:
        cnt = 0
        ind += 1

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

import math
import itertools

k = int(input())
k_list = []
for i in range(1, k+1):
  k_list.append(i)

total = 0
for i in list(itertools.product(k_list,repeat=3)):
  total += math.gcd(i[0],math.gcd(i[1],i[2]))
  
print(total)

### FIXED CODE ###

import math

k = int(input())

total = 0
for a in range(1, k+1):
  for b in range(1, k+1):
    if math.gcd(a,b) == 1:
      total += k
    else:
      for c in range(1, k+1):
        total += math.gcd(a,math.gcd(b,c))
    
print(total)
### BUGGY CODE ###

# coding: utf-8
H, N = map(int, input().split())
L = []
for i in range(N):
    L.append(list(map(int, input().split())))
dp = [float("inf") for _ in range(H+1)] 
dp[0] = 0
for i in range(1, H+1):
    for j in range(N):
        a, b = L[j]
        if i <= a:
            dp[i] = min(dp[i], b)
        else:
            dp[i] = min(dp[i], dp[i-a] + b)
    # print(*dp)
print(dp[H])

### FIXED CODE ###

# coding: utf-8
H, N = map(int, input().split())
L = []
for i in range(N):
    L.append(list(map(int, input().split())))
dp = [float("inf") for _ in range(H+1)] 
dp[0] = 0
top = 10**9
for i in range(1, H+1):
    for j in range(N):
        a, b = L[j]
        if i <= a:
            dp[i] = min(dp[i], b)
        else:
            dp[i] = min(dp[i], dp[i-a] + b)
    # print(*dp)
print(dp[H])
### BUGGY CODE ###

N=int(input())
m=[]
ans=0
for _ in range(N):
    a=int(input())
    m+=[a]
    if m.count(a) % 2 == 1:
        ans+=1
    else:
        ans-=1

print(ans)


### FIXED CODE ###

N=int(input())
m={}
for _ in range(N):
    a=int(input())
    if a in m:
        if m[a] == 0:
            m[a] = 1
        else:
            m[a] = 0
    else:
        m[a]=1

ans=sum(m.values())

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

from bisect import*
def main():
    root=[[],[]]
    def search_higher(key):
        ptr=root
        ret=None
        while ptr[1]:
            i=bisect(ptr[0],key)
            if i!=len(ptr[0]):ret=ptr[0][i]
            ptr=ptr[1][i]
        i=bisect(ptr[0],key)
        if i!=len(ptr[0]):ret=ptr[0][i]
        return ret
    def search_lower(key):
        ptr=root
        ret=None
        while ptr[1]:
            i=bisect_left(ptr[0],key)
            if i!=0:ret=ptr[0][i-1]
            ptr=ptr[1][i]
        i=bisect_left(ptr[0],key)
        if i!=0:ret=ptr[0][i-1]
        return ret
    def insert_rec(ptr,key):
        b_size=8192
        if not ptr[1]:
            insort(ptr[0],key)
            if len(ptr[0])==b_size*2-1:
                ret=[ptr[0][:b_size],[]]
                ptr[0]=ptr[0][b_size:]
                return ret
        else:
            i=bisect(ptr[0],key)
            tmp=insert_rec(ptr[1][i],key)
            if tmp:
                ptr[0].insert(i,tmp[0].pop())
                ptr[1].insert(i,tmp)
                if len(ptr[1])==b_size*2:
                    ret=[ptr[0][:b_size],ptr[1][:b_size]]
                    ptr[0],ptr[1]=ptr[0][b_size:],ptr[1][b_size:]
                    return ret
    def insert(key):
        tmp=insert_rec(root,key)
        if tmp:root[0],root[1]=[tmp[0].pop()],[tmp,root]
    n,*a=map(int,open(0).read().split())
    l=[0]*n
    for i,v in enumerate(a,1):l[v-1]=i
    insert(0)
    insert(n+1)
    c=0
    for i,v in enumerate(l,1):
        c+=(search_higher(v)-v)*(v-search_lower(v))*i
        insert(v)
    print(c)
main()

### FIXED CODE ###

root=lambda x:x if par[x]==x else root(par[x])
same=lambda x,y:root(x)==root(y)
def unite(*z):
  x,y=map(root,z)
  if x!=y:
    if rank[x]<rank[y]:
      par[x]=y
      size[y]+=size[x]
    else:
      par[y]=x
      size[x]+=size[y]
      if rank[x]==rank[y]:rank[x]+=1
n,*a=map(int,open(0).read().split())
*par,=range(n)
rank=[1]*n
size=[1]*n
b=[0]*n
for i,t in enumerate(a):b[t-1]=i
c=0
for k in b[::-1]:
  l=r=1
  if k>0 and a[k-1]>a[k]:
    l+=size[root(k-1)]
    unite(k-1,k)
  if k+1<n and a[k+1]>a[k]:
    r+=size[root(k+1)]
    unite(k+1,k)
  c+=l*r*a[k]
print(c)
### BUGGY CODE ###

import bisect
N = int(input())
A = list(map(int,input().split()))
ans = 0
for i in range(N):
    l = 1
    for j in range(i-1,-1,-1):
        if A[i] <= A[j]:
            l += 1
        else:
            break
    r = 1
    for j in range(i+1,N):
        if A[i] <= A[j]:
            r += 1
        else:
            break
    ans += l*r*A[i]
print(ans)

### FIXED CODE ###

N = int(input())
a = list(map(int,input().split()))
l = [i for i in range(N)]
r = [i for i in range(N)]

b = [0] * N
for i in range(N):
    b[a[i]-1] = i

ans = 0
for i in range(N-1,-1,-1):
    m = b[i]
    x,y = l[m],r[m]
    ans += (i+1)*(m-x+1)*(y-m+1)
    l[min(y+1,N-1)] = x
    r[max(x-1,0)] = y
print(ans)
### BUGGY CODE ###

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

processed = list(map(lambda x: (1+x)/2, num_array))

expected = []
for i in range(len(num_array) - M + 1):
    expected.append(sum(processed[i:i+M]))

print(max(expected)) 

### FIXED CODE ###

import numpy as np

N, M = list(map(int, input().split()))
num_array = np.cumsum(list(map(lambda x: (x+1)/2, list(map(int, input().split())))))

max_exp = num_array[M-1]
for i in range(len(num_array)-M):
    tmp = num_array[i+M] - num_array[i]
    if max_exp < tmp:
        max_exp = tmp

print(max_exp)
### BUGGY CODE ###

k = int(input())
a, b = map(int, input().split())
l = 1
while a > l*k:
    l += 1
m = 1
while b < m*k:
    m += 1
    
if a <= l*k <= b or a <= m*k <= b:
    print("OK")
else:
    print("NG")

### FIXED CODE ###

n = int(input())
a, b = map(int, input().split())
k = 1
while True:
    if a <= n*k <= b:
        print("OK")
        exit()
    elif n*k > b:
        print("NG")
        exit()
    else:
        k += 1
### BUGGY CODE ###

N = int(input())
X = list(map(int,input().split()))
ans = 0
mod = 10**9+7
l=[1]*(N+1)
a=1
for i in range(2,N+1):
  a*=i
  a%=mod
  l[i]=a
x=X[-1]
for i in range(N-1):
  for j in range(i+1,N-1):
    a = j-i-1
    ans += (X[j]-X[i])*(l[a])%mod*l[N-1]%mod*pow(l[a+2],mod-2,mod)%mod
    
for k,y in enumerate(X[:N-1:]):
  a = N-k-2
  ans+=(x-y)*l[a]%mod*l[N-1]%mod*pow(l[a+1],mod-2,mod)%mod
print(ans%mod)


### FIXED CODE ###

N = int(input())
X = list(map(int,input().split()))
import math
ans = 0
mod = 10**9+7
a = 0
ans = 0
for i in range(N-1):
  a += pow(i+1,mod-2,mod)
  ans += ((X[i+1]-X[i])%mod)*(a%mod)
  ans %= mod
  
ans *= math.factorial(N-1)%mod

print(ans%mod)
### BUGGY CODE ###

import itertools
import fractions as math

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

def main():
    a, b = map(int, input().split())
    k = []
    for i in make_divisors(a):
        if i > b:
            break
        elif b % i == 0:
            k.append(i)
    count = 0
    for i in itertools.product([0,1], repeat=len(k)):
        if i.count(1) < 1:
            continue
        l = [k[j[0]] for j in enumerate(i) if j[1] == 1]
        for x, y in itertools.combinations(l, 2):
            if math.gcd(x, y) != 1:
                break
        else:
            count = max(count, len(l))
    print(count)
                
if __name__ == '__main__':
    main()

### FIXED CODE ###

from functools import lru_cache

def main():
    a,b=map(lambda x: set(prime_factorize(int(x))),input().split())
    print(len(a&b)+1)

@lru_cache(maxsize=None)
def primes(n:int) -> list:
    '''n以下の全素数をlistで返す'''
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]

# 素数判定（単純な素数判定なら十分早い。大量にやる場合はX in primesがよさそう）
@lru_cache(maxsize=None)
def is_prime(n: int) -> bool:
    '''引数nが素数であればTrue、そうでなければFalseを返す'''
    if n == 1:
        return False
    elif n == 2:
        return True
    elif n % 2 == 0:
        return False
    
    for i in range(3, int(n**0.5)+1, 2):
        if n % i == 0:
            return False
    return True

# 素因数分解
@lru_cache(maxsize=None)
def prime_factorize(n: int) -> list:
    '''引数nの素因数分解結果のlistを返す。'''
    arr = []
    # 2で割り続け奇数まで還元する
    while n % 2 == 0:
        arr.append(2)
        n //= 2
    # sqrt(n)までの素数で試し割
    for f in primes(int(n**0.5)):
        while n % f == 0:
            arr.append(f)
            n //= f
    if n != 1:
        arr.append(n)
    return arr

#約数リスト
def make_divisors(n: int) -> list:
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]
        
if __name__ == "__main__":
    main()
### BUGGY CODE ###

p=[]
q=[]
n,m = map(int,input().split())
for _ in [0]*m:
  a,b = map(int,input().split())
  if a == 1:
    p += [b]
  elif b == n:
    q += [a]
for x in p:
  if x in q:
    print("POSSIBLE")
    exit()
print("IMPOSSIBLE")

### FIXED CODE ###

p=[]
q=[]
n,m = map(int,input().split())
for _ in [0]*m:
  a,b = map(int,input().split())
  if a == 1:
    p += [b]
  elif b == n:
    q += [a]
p.sort()
q.sort()
i,j = 0,0
while i<len(p) and j<len(q):
    if p[i]<q[j]:
      i += 1
    elif p[i]>q[j]:
      j += 1
    else:
      print("POSSIBLE")
      exit()
print("IMPOSSIBLE")
### BUGGY CODE ###

from itertools import*;N,M,R=map(int,input().split())
r=map(int,input().split());G=[[9e9]*N for _ in[0]*N]
for _ in[0]*M:A,B,C=map(int,input().split());G[A-1][B-1]=G[B-1][A-1]=C
for i in range(N):
 for j in range(N):
  for k in range(N):G[j][k]=min(G[j][k],G[j][i]+G[i][k])
print(min(sum(G[i-1][j-1]for i,j in zip(t,t[1:]))for t in permutations(r)))

### FIXED CODE ###

from itertools import*;from scipy.sparse import*
N,M,R=map(int,input().split());r=map(int,input().split())
G=[[9e9]*N for _ in[0]*N]
for _ in[0]*M:A,B,C=map(int,input().split());G[A-1][B-1]=G[B-1][A-1]=C
D=csgraph.dijkstra(csr_matrix(G))
print(int(min(sum(D[i-1,j-1]for i,j in zip(t,t[1:]))for t in permutations(r))))
### BUGGY CODE ###

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

for i in range(n):
    if i + k >= n:
        exit()
    a = A[i:i+k]
    pre = a[0]
    aft = A[i+k]
    if pre >= aft:
        print('No')
    else:
        print('Yes')



### FIXED CODE ###

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

for i in range(n):
    if i + k >= n:
        exit()
    pre = A[i]
    aft = A[i+k]
    if pre >= aft:
        print('No')
    else:
        print('Yes')
### BUGGY CODE ###

N = int(input())
A_list = list(map(int,input().split()))
Q = int(input())
S =sum(A_list)
for i in range(Q):
    B,C = map(int,input().split())
    count = 0
    for j in A_list:
        if j == B:
            A_list[A_list.index(j)] = C
            count += 1
    S = S + count * (C - B)
    print(S)

### FIXED CODE ###

N = int(input())
A_list = list(map(int,input().split()))
Q = int(input())
S = sum(A_list)
count_list = [0] * (10 ** 5 + 1)
for A in A_list:
    count_list[A] += 1 
for i in range(Q):
    B,C = map(int,input().split())
    S = S + count_list[B] * (C - B)
    count_list[C] += count_list[B]
    count_list[B] = 0
    print(S)
#    print(sum(A_list))