Problem:


Score : 400 points

Problem Statement

You have a sequence A composed of N positive integers: A_{1}, A_{2}, \cdots, A_{N}.

You will now successively do the following Q operations:

In the i-th operation, you replace every element whose value is B_{i} with C_{i}.

For each i (1 \leq i \leq Q), find S_{i}: the sum of all elements in A just after the i-th operation.

Constraints

All values in input are integers.

 1 \leq N, Q, A_{i}, B_{i}, C_{i} \leq 10^{5} 

 B_{i} \neq C_{i} 

Input

Input is given from Standard Input in the following format:

N
A_{1} A_{2} \cdots A_{N}
Q
B_{1} C_{1}
B_{2} C_{2}
\vdots
B_{Q} C_{Q}

Output

Print Q integers S_{i} to Standard Output in the following format:

S_{1}
S_{2}
\vdots
S_{Q}

Note that S_{i} may not fit into a 32-bit integer.

Sample Input 1

4
1 2 3 4
3
1 2
3 4
2 4

Sample Output 1

11
12
16

Initially, the sequence A is 1,2,3,4.

After each operation, it becomes the following:

2, 2, 3, 4

2, 2, 4, 4

4, 4, 4, 4

Sample Input 2

4
1 1 1 1
3
1 2
2 1
3 5

Sample Output 2

8
4
4

Note that the sequence A may not contain an element whose value is B_{i}.

Sample Input 3

2
1 2
3
1 100
2 100
100 1000

Sample Output 3

102
200
2000



Sample input:
4
1 2 3 4
3
1 2
3 4
2 4


Sample output:
11
12
16

Submission status: Accepted

Solution code:
# 2020/06/21
# AtCoder Beginner Contest 171 - D

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

# al = [0] * (10 ** 2 + 1)
al = [0] * (10 ** 5 + 1)
sum = 0

# Sum and Count
for i in range(n):
    al[a[i]] = al[a[i]] + 1
    sum = sum + a[i]

# Output question
q = int(input())
chg = 0
for i in range(q):
    b, c = map(int,input().split())
    chg = -1 * b * al[b]
    chg = chg + al[b] * c
    sum = sum + chg
    print(sum)
    al[c] = al[c] + al[b]
    al[b] = 0

Submission status: Accepted

Solution code:
from collections import defaultdict

n = int(input())
a = list(map(int, input().split()))
q = int(input())
bc = [list(map(int, input().split())) for i in range(q)]

ans = sum(a)
dic = defaultdict(int)
for i in a:
    dic[i] += 1
for b,c in bc:
    if dic[b] == 0:
        print(ans)
        continue
    ans += (c-b) * dic[b]
    print(ans)
    dic[c] += dic[b]
    dic[b] = 0

Submission status: Accepted

Solution code:
from collections import Counter
N = int(input())
A = list(map(int,input().split()))
s = sum(A)
Q = int(input())
c = Counter(A)
for _ in range(Q):
    B,C = map(int,input().split())
    s -= B*c[B]
    s += C*c[B]
    c[C] += c[B]
    c[B] = 0
    print(s)

Submission status: Accepted

Solution code:
import collections
n = int(input())
a = list(map(int, input().split()))
c = collections.Counter(a)
ans = sum(a)
d = {}
q = int(input())
for i in range(q):
    x, y = map(int, input().split())
    ans -= c[x] * x
    ans += c[x] * y
    c[y] = c[y] + c[x]
    c[x] = 0
    print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

n=int(input())
a=Counter(list(map(int,input().split())))
q=int(input())
sm=0
for x in a:
    sm+=x*a[x]

for i in range(q):
    b,c=map(int,input().split())
    if b in a:
        a[c]+=a[b]
        sm+=(c-b)*a[b]
        a[b]=0
    print(sm)

Submission status: Accepted

Solution code:

from collections import defaultdict
d = defaultdict(int) 
n=int(input())
a=list(map(int,input().split()))
q=int(input())

L=[]

for key in a:
    d[key] += 1
# for i in range(len(a)):
#     L.append(a[i])
#     d[a[i]]+=1
#     L.append(d)
s=0
# for k,v in enumerate(dict(d)):
#     s+=k*v
#     L.append(s)
s=sum(a)

for j in range(q):

    b,c=map(int,input().split())
    s+=d[b]*(c-b)
    d[c]+=d[b]
    d[b]=0
    L.append(s)
for j in range(len(L)):
    print(L[j])

Submission status: Accepted

Solution code:
N = int(input())
arr = list(map(int, input().split()))
target = [0]*(10**5+1)
for i in arr:
    target[i] += 1
ans = sum(arr)
Q = int(input())
for i in range(Q):
    B, C = map(int, input().split())
    target[C] += target[B]
    ans += target[B]*C
    ans -= target[B]*B
    target[B] = 0
    print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

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

d = defaultdict(int)
for a in A:
    d[a] += 1

Q = int(input())
total = sum(A)
for _ in range(Q):
    b, c = map(int, input().split())
    if b not in d:
        print(total)
    else:
        total += (c - b) * d[b]
        d[c] += d[b]
        d[b] = 0
        print(total)

Submission status: Accepted

Solution code:
from collections import defaultdict

n=int(input())
a=[int(_) for _ in input().split()]
q=int(input())
dic=defaultdict(lambda :0 )
for i in a:
    dic[i]+=1
ans = sum(a)
for i in range(q):
    b,c=[int(_) for _ in input().split()]
    ans +=(c-b)*dic[b]
    print(ans)
    dic[c]+=dic[b]
    dic[b]=0

Submission status: Accepted

Solution code:
t=1
while t:
	t-=1
	n=int(input())
	# n,m=(map(int,input().split()))
	l=list(map(int,input().split()))
	c=[0 for i in range(100001)]
	sumi=sum(l)
	for i in range(n):
		c[l[i]]+=1
	q=int(input())
	while(q):
		q-=1
		a,b=map(int,input().split())
		sumi+=(c[a]*(b-a))
		c[b]+=c[a]
		c[a]=0
		print(sumi)

Submission status: Accepted

Solution code:
N = int(input())
A_list = [int(e) for e in input().split()]

A_dict = dict()
S = 0

for A in A_list:
    if A not in A_dict:
        A_dict[A] = 0
        
    A_dict[A] += 1
    S += A

Q = int(input())

for i in range(1,Q+1):
    B,C = map(int, input().split())
    
    if B in A_dict:
        if C not in A_dict:
            A_dict[C] = A_dict[B]
        else:
            A_dict[C] += A_dict[B]
            
        S -= B*A_dict[B]
        S += C*A_dict[B]

        A_dict[B] = 0
        
    print(S)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
Q = int(input())
b_list = []
c_list = []

for i in range(Q):
    b, c = list(map(int, input().split()))
    b_list.append(b)
    c_list.append(c)
data = dict()
for a in A:
    if a in data:
        data[a] += 1
    else:
        data[a] = 1
ans = sum(A)
for i in range(Q):
    if b_list[i] in data:
        ans += (c_list[i] - b_list[i]) * data[b_list[i]]
        num = data.pop(b_list[i])
        if c_list[i] in data:
            data[c_list[i]] += num
        else:
            data[c_list[i]] = num
    print(ans)

Submission status: Accepted

Solution code:
n = int(input())
l = [0 for _ in range(100001)]
s = 0
for a in input().split():
    l[int(a)] += 1
    s += int(a)
q = int(input())
ans = []
for i in range(q):
    b,c = map(int,input().split())
    s += (c-b)*l[b]
    ans.append(s)
    l[c] += l[b]
    l[b] = 0

for k in ans:
    print(k)

Submission status: Accepted

Solution code:
from collections import Counter

n = int(input())
a = [int(i) for i in input().split()]
q = int(input())
bc = [[int(i) for i in input().split()] for _ in range(q)]

cnt = Counter(a)
s = sum(a)
for b, c in bc:
    s += (c - b) * cnt[b]
    cnt[c] += cnt[b]
    cnt[b] = 0
    print(s)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
Q = int(input())
BC = [list(map(int, input().split())) for _ in range(Q)]

cnt = {}
for i, Ai in enumerate(A):
    cnt.setdefault(str(Ai), 0)
    cnt[str(Ai)] += 1

ans = 0
for key, val in cnt.items():
    num = int(key)
    ans += num * val

for j, (Bj, Cj) in enumerate(BC):
    key_B = str(Bj)
    cnt.setdefault(key_B, 0)
    val_B = cnt[key_B]
    cnt[key_B] = 0
    ans -= Bj * val_B
    #
    key_C = str(Cj)
    cnt.setdefault(key_C, 0)
    cnt[key_C] += val_B
    ans += Cj * val_B
    #
    print(ans)

Submission status: Accepted

Solution code:
n = int(input())
dp = [0 for _ in range(10**5)]
a = list(map(int, input().split()))
Sum = sum(a)
for i in a:
  dp[i-1] += 1
  
q = int(input())
for i in range(q):
  sa, sb = map(int, input().split())
  x = dp[sa-1]
  dp[sa-1] = 0
  Sum -= x*sa
  dp[sb-1] += x
  Sum += x*sb
  print(Sum)

Submission status: Accepted

Solution code:
from collections import defaultdict

n = int(input())
a = list(map(int,input().split()))
ans = sum(a)
d = defaultdict(int)
for i in a:
    d[i] += 1

q = int(input())
for _ in range(q):
    b,c = map(int,input().split())
    count = d[b]
    ans += (c-b)*count
    print(ans)
    d[b] = 0
    d[c] += count

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
q = int(input())
b = list(list(map(int, input().split())) for i in range(q))
dic = {}
for i in range(n):
    if a[i] not in dic.keys():
        dic[a[i]] = 1
    else:
        dic[a[i]] += 1
su = sum(a)
for i in range(q):
    if b[i][0] not in dic.keys():
        pass
    else:
        su += (b[i][1]-b[i][0])*dic[b[i][0]]
        if b[i][1] not in dic.keys():
            dic[b[i][1]] = 0
        dic[b[i][1]] += dic[b[i][0]]
        dic[b[i][0]] = 0
    print(su)

Submission status: Accepted

Solution code:
from collections import Counter
n = int(input())
A = list(map(int,input().split()))
q = int(input())
Count = Counter(A)
s = sum(A)
B = []
C = []
for i in range(q):
    b,c = map(int,input().split())
    B.append(b)
    C.append(c)
for i in range (q):
    s += (C[i]-B[i])*Count[B[i]]
    print(s)
    Count[C[i]] += Count[B[i]]
    Count[B[i]] = 0

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    A = list(map(int, input().split()))
    Q = int(input())
    BC = [list(map(int, input().split())) for _ in range(Q)]
    
    S = sum(A)

    A_map = {}
    for a in A:
        if a in A_map:
            A_map[a] += 1
        else:
            A_map[a] = 1

    for b,c in BC:
        if b not in A_map:
            print(S)
            continue

        num = A_map.pop(b)
        if c in A_map:
            A_map[c] += num
        else:
            A_map[c] = num

        S -= b * num
        S += c * num
        print(S)
main()

Submission status: Accepted

Solution code:
from collections import Counter

N = int(input())
A = list(map(int, input().split()))
counts = Counter(A)
Q = int(input())
cur = sum(A)
for _ in range(Q):
    B, C = map(int, input().split())
    if B in counts:
        cur -= counts[B] * B
        cur += counts[B] * C
        print(cur)
        counts[C] += counts[B]
        del counts[B]
    else:
        print(cur)

Submission status: Accepted

Solution code:
big = 10**5 + 1

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

B, C = [0]*Q, [0]*Q
for i in range(Q):
    B[i], C[i] = map(int, input().split())

counts = [0]*big
total = 0
for Ai in A:
    counts[Ai] += 1
    total += Ai

for i in range(Q):
    Bi, Ci = B[i], C[i]
    total += (Ci - Bi)*counts[Bi]

    counts[Ci] += counts[Bi]
    counts[Bi] = 0
    print(total)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
n = int(input())
a = list(map(int, input().split()))
q = int(input())
b = [0]*q
c = [0]*q
for i in range(q):
    b[i], c[i] = map(int, input().split())

sum_i = 0
map_ai = [0]*100001
for ai in a:
    sum_i += ai
    map_ai[ai] += 1

for i in range(q):
    bi = b[i]
    ci = c[i]
    num_bi = map_ai[bi]
    sum_i -= (bi-ci) * num_bi
    print(sum_i)
    map_ai[bi] -= num_bi
    map_ai[ci] += num_bi

Submission status: Accepted

Solution code:
n = int(input())
lst = list(map(int,input().split(' ')))
q = int(input())
bc = [list(map(int,input().split(' '))) for _ in range(q)]

cnt = [0] * (10**5+1)
for l in lst:
    cnt[l] += 1

calc = sum(lst)
for d in bc:
    buf = cnt[d[0]]
    cnt[d[1]] += buf
    cnt[d[0]] = 0
    calc += buf * (d[1] - d[0])
    print(calc)

Submission status: Accepted

Solution code:
from collections import Counter


def main():
    N = int(input())
    A = list(map(int, input().split()))
    C = Counter(A)
    S = sum(A)
    Q = int(input())
    for _ in range(Q):
        b, c = map(int, input().split())
        if C[b] > 0:
            cb = C[b]
            S -= b*cb
            S += c*cb
            C[b] = 0
            C[c] += cb
        print(S)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N = int(input())
As = list(map(int,input().split()))
Q = int(input())

lst = [0] * (10**5+1)
for A in As:
    lst[A] += 1

val = sum(As)

vals = []
for i in range(Q):
    B, C = map(int,input().split())
    val += (C-B) * lst[B]
    lst[C] += lst[B]
    lst[B] = 0
    vals.append(val)
for val in vals:
    print(val)

Submission status: Accepted

Solution code:
from collections import defaultdict


def main():
    N = int(input())
    A = list(map(int, input().split()))
    Q = int(input())
    d = defaultdict(int)
    s = sum(A)
    for a in A:
        d[a] += 1
    
    for i in range(Q):
        B, C = map(int, input().split())
        num = d[B]
        d[B] = 0
        d[C] += num
        s += num * (C - B)
        print(s)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
b = {}
for x in a:
  try:
    if b[x]:
      b[x] += 1
  except:
    b[x] = 1
#print(b)
ans = sum(a)
q = int(input())
for _ in range(q):
  x,y = map(int,input().split())
  try:
    if b[x] != -1:
      bx = b[x]
      b[x] = 0
  except:
    #print(b)
    print(ans)
    continue
  try:
    if b[y] != -1:
      b[y] += bx
  except:
    b[y] = bx
  #print(b)
  ans += bx * (y-x)
  print(ans)

Submission status: Accepted

Solution code:
# input()
# int(input())
# map(int, input().split())
# list(map(int, input().split()))
# list(map(int, list(input()))) # スペースがない数字リストを読み込み
import math
import fractions
import sys
import bisect
import heapq  # 優先度付きキュー(最小値取り出し)
import collections
from collections import Counter
from collections import deque
import pprint

sr = lambda: input()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

"""nを素因数分解"""
"""2以上の整数n => [[素因数, 指数], ...]の2次元リスト"""


def factorization(n):
    arr = []
    temp = n
    if n == 1:
        return arr

    for i in range(2, int(-(-n ** 0.5 // 1)) + 1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr.append([i, cnt])

    if temp != 1:
        arr.append([temp, 1])

    if arr == []:
        arr.append([n, 1])

    return arr


# a^n
def power(a, n, mod):
    x = 1
    while n:
        if n & 1:
            x *= a % mod
        n >>= 1
        a *= a % mod
    return x % mod


# n*(n-1)*...*(l+1)*l
def kaijo(n, l, mod):
    if n == 0:
        return 1
    a = n
    tmp = n - 1
    while (tmp >= l):
        a = a * tmp % mod
        tmp -= 1
    return a


inf = 10 ** 18
mod = 10 ** 9 + 7

n = ir()
a = lr()
q = ir()
dic = Counter(a)
total = sum(a)
for i in range(q):
    b,c = lr()
    if c in dic:
        dic[c] += dic[b]
    else:
        dic[c] = dic[b]
    total += (c-b)*dic[b]
    dic[b] = 0
    print(total)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

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

sm = 0
d = {}
for a in A:
    if a in d:
        d[a] += 1
    else:
        d[a] = 1
    sm += a

for _ in range(Q):
    b, c = map(int, input().split())
    if b in d:
        sm += (c-b) * d[b]
        if c in d:
            d[c] += d[b]
        else:
            d[c] = d[b]
        d.pop(b)
    print(sm)

Submission status: Accepted

Solution code:
from collections import Counter


def read_int():
    return int(input().strip())


def read_ints():
    return list(map(int, input().strip().split(' ')))


def solve():
    N = read_int()
    counter = Counter(read_ints())
    T = sum(k*v for (k, v) in counter.items())
    Q = read_int()
    for _ in range(Q):
        b, c = read_ints()
        b_count = counter[b]
        counter[b] = 0
        counter[c] += b_count
        T = T-b*b_count+c*b_count
        print(T)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    A = list(map(int, input().split()))
    Q = int(input())
    D = [0] * (10**5+1)
    for i in range(N):
        D[A[i]] += 1

    ans = sum(A)
    for _ in range(Q):
        B, C = map(int, input().split())
        if D[B] != 0:
            ans -= B * D[B]
            ans += D[B] * C
            D[C] += D[B]
            D[B] = 0
            print(ans)
        else:
            print(ans)




if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
from collections import Counter, defaultdict

n = int(sys.stdin.buffer.readline())
aaa = list(map(int, sys.stdin.buffer.readline().split()))
q = int(sys.stdin.buffer.readline())
bc = map(int, sys.stdin.buffer.read().split())

cnt = defaultdict(int, Counter(aaa))
ans = sum(a * c for a, c in cnt.items())
buf = []

for b, c in zip(bc, bc):
    if b not in cnt:
        buf.append(ans)
        continue
    ans += cnt[b] * (c - b)
    cnt[c] += cnt[b]
    del cnt[b]
    buf.append(ans)

print('\n'.join(map(str, buf)))

Submission status: Accepted

Solution code:
def resolve():
    n=int(input())
    a=list(map(int,input().split()))
    l=[0]*(10**5+1)
    for i in a:
        l[i]+=1
    ans=sum(a)
    q=int(input())
    for i in range(q):
        b,c=map(int,input().split())
        x=l[b]
        ans+=(c-b)*x
        l[c]+=x
        l[b]=0
        print(ans)

if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
n = int(input())
a = [int(x) for x in input().split()]
q = int(input())
from collections import Counter
f = Counter(a)
t = sum(a)

for i in range(q):
    b, c = map(int, input().split())
    t += (c - b) * f[b]
    f[c] += f[b]
    f[b] = 0
    print(t)

Submission status: Accepted

Solution code:
import collections
n=int(input())
a=list(map(int,input().split()))
q=int(input())
bc=[list(map(int,input().split())) for i in range(q)]
ac=collections.Counter(a)
#print(ac)
ans=sum(a)
for i in range(q):
    if ac[bc[i][0]]!=None:
        if ac[bc[i][1]]!=None:
            ans-=bc[i][0]*ac[bc[i][0]]
            ans+=bc[i][1]*ac[bc[i][0]]
            ac[bc[i][1]]+=ac[bc[i][0]]
            ac[bc[i][0]]=0
        else:
            ans-=bc[i][0]*ac[bc[i][0]]
            ans+=bc[i][1]*ac[bc[i][0]]
            ac[bc[i][1]] = ac[bc[i][0]]
            ac[bc[i][0]]=0

    print(ans)

Submission status: Accepted

Solution code:
counter = {}
start_sum = 0
n = int(input())
a_list = list(map(int, input().split()))
q = int(input())
b_list, c_list = [], []
for _ in range(q):
    b_in, c_in = map(int, input().split())
    b_list.append(b_in)
    c_list.append(c_in)
    counter[b_in] = 0
    counter[c_in] = 0
    

for a in a_list:
    start_sum += a
    if not (counter.get(a) is None):
        counter[a] += 1

for b, c in zip(b_list, c_list):
    counter[c] += counter[b]
    start_sum += (c-b)*counter[b]
    counter[b] = 0
    print(start_sum)

Submission status: Accepted

Solution code:
from collections import defaultdict


N = int(input())
input_list = list(map(int, input().split()))
a_list = sorted(input_list)

a_sum = sum(a_list)
a_dict = defaultdict(int)
for a in a_list:
    a_dict[a] += 1

Q = int(input())
b_list, c_list = [], []
for _ in range(Q):
    input_list = list(map(int, input().split()))
    b, c = input_list
    
    replace_time = a_dict[b]
    a_dict[c] += a_dict[b]
    a_dict[b] = 0
    
    a_sum += c * replace_time - b * replace_time    
    print(a_sum)

Submission status: Accepted

Solution code:
import numpy as np

N = int(input())
lis = np.zeros(10**5)

As = np.array(input().split()).astype(np.int64)
NUM = As.sum()

for n in As:
  lis[n-1] += 1

Q = int(input())
for q in range(Q):
  B, C = map(int, input().split())
  nnn = lis[B-1]
  lis[B-1] = 0
  lis[C-1] += nnn
  NUM = NUM - B*nnn + C*nnn
  print(int(NUM))

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
q=int(input())

s=sum(a)
d=[0]*(10**5+1)
for i in a:
    d[i-1]+=1

for _ in range(q):
    b,c=map(int,input().split())
    tmp=0
    k=d[b-1]
    d[c-1]+=k
    d[b-1]=0

    tmp = k*c-k*b
    s+=tmp
    print(s)

Submission status: Accepted

Solution code:
import collections
N = int(input())
A = list(map(int,input().split()))
ans = sum(A)
d = collections.Counter(A)
Q = int(input())
for i in range(Q):
    B,C = map(int,input().split())
    b = d[B]
    ans = ans + (C-B)*b
    print(ans)
    d[B] = 0
    d[C] = d[C] + b

Submission status: Accepted

Solution code:
def ii():return int(input())
def iim():return map(int,input().split())
def iil():return list(map(int,input().split()))

from collections import Counter

n = ii()
A = iil()
s = sum(A)
d = Counter(A)

q = ii()

for i in range(q):
    b,c = iim()
    m = d.pop(b,0)
    if m:
        d[c] = d.get(c,0)+m
    s += (c-b)*m
    print(s)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache


#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)


#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1:
    arr.append([temp, 1])
  if arr==[]:
    arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n -1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n:
    return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############
N = I()
A = IL()
Q = I()

dic = DD(int)
for a in A:
  dic[a] += 1
  
ans = 0
for i in range(10**5+1):
  ans += dic[i]*i
  
for _ in range(Q):
  b,c = IL()
  ans -= dic[b]*b
  ans += dic[b]*c
  print(ans)
  dic[c] += dic[b]
  dic[b] = 0

Submission status: Accepted

Solution code:
from collections import Counter
input()
a = [int(x) for x in input().split()]

sum_ = sum(a)
d = Counter(a)

q = int(input())
for i in range(q):
    # print(d)
    b, c = map(int, input().split())
    n = d[b]
    d[b] = 0
    if(c in d):
        d[c] += n
    else:    
        d[c] = n
    
    print(sum_ + n * (c - b))
    sum_ += n * (c - b)

Submission status: Accepted

Solution code:
from collections import defaultdict
n=int(input())
num_dict=defaultdict(int)
a_sum=0
for a in map(int,input().split()):
    num_dict[a]+=1
    a_sum+=a
for i in range(int(input())):
    b,c=map(int,input().split())
    a_sum+=c*num_dict[b]-b*num_dict[b]
    num_dict[c]+=num_dict[b]
    num_dict[b]=0
    print(a_sum)

Submission status: Accepted

Solution code:
import sys
import collections
sys.setrecursionlimit(10**6)


def main(input, print):
    n = int(input())
    a = list(map(int, input().split()))
    counter = collections.Counter(a)
    q = int(input())
    sum = 0
    for key in counter:
        sum += key * counter[key]
    for i in range(q):
        b, c = map(int, input().split())
        cnt = counter[b]
        del counter[b]
        counter[c] += cnt
        sum += (c-b)*cnt

        print(sum)


if __name__ == '__main__':
    main(sys.stdin.readline, print)

Submission status: Accepted

Solution code:
from collections import defaultdict

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

D = defaultdict(int)
S = 0

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

for _ in range(Q):
  B, C = map(int, input().split())
  r = D[B]
  D[B] = 0
  D[C] += r
  S += (C - B)*r
  print(S)

Submission status: Accepted

Solution code:
from collections import Counter

n = int(input())
a_array = [int(x) for x in input().split()]
d = Counter(a_array)
res = 0
for key, value in d.items():
    res += key * value
q = int(input())
bc_array = [[int(x) for x in input().split()] for y in range(q)]
for b, c in bc_array:
    d.setdefault(b, 0)
    res -= b * d[b]
    res += c * d[b]
    print(res)
    d[c] += d[b]
    d[b] = 0

Submission status: Accepted

Solution code:
n = int(input())
A = list(map(int,input().split()))
m = int(input())
Q = [list(map(int,input().split())) for _ in range(m)]
L = [0 for _ in range(10**5+1)]
for a in A:
    L[a]+=1
ans = sum(A)

for q in Q:
    num_b = L[q[0]]
    L[q[0]] -= num_b    
    L[q[1]] += num_b
    ans -= (num_b)*q[0]
    ans += (num_b)*q[1]
    print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
s = sum(a)
x = [0 for _ in range(10**5+1)]
for ai in a:
  x[ai] += 1
q = int(input())
for _ in range(q):
  b,c = map(int,input().split())
  xb = x[b]
  x[b] = 0
  s+= xb*(c-b)
  x[c] += xb
  print(s)

Submission status: Accepted

Solution code:
n = int(input())
li_a = list(map(int, input().split()))
q = int(input())
sum_ = sum(li_a)
di = {}
for i in range(1, 10**5+1):
    di[i] = 0
for i in li_a:
    di[i] += 1
for _ in range(q):
    b, c = map(int, input().split())
    tmp = di[b]
    di[b] = 0
    di[c] += tmp
    sum_ = sum_ + c*tmp - b*tmp
    print(sum_)

Submission status: Accepted

Solution code:
import collections
N = int(input())
A = list(map(int,input().split()))
counter = collections.Counter(A)
ans = sum(A)
Q = int(input())
R = []
for _ in range(Q):
    b,c = map(int,input().split())
    ans += (c-b)*counter[b]
    counter[c] +=counter[b]
    del counter[b]
    R.append(ans)
for r in R:
    print(r)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import Counter

n = int(input())
a = list(map(int, input().split()))
q = int(input())
cnt = Counter(a)
s = sum(a)
for _ in range(q):
    b, c = map(int, input().split())
    s += (c - b) * cnt[b]
    cnt[c] += cnt[b]
    cnt[b] = 0
    print(s)

Submission status: Accepted

Solution code:
from collections import Counter
import sys
input = sys.stdin.readline

n = int(input())
a = list(map(int, input().split()))
q = int(input())
bc = [list(map(int, input().split())) for _ in range(q)]

ans = sum(a)
a = Counter(a)
for b, c in bc:
    ans = ans + (c - b) * a[b]
    a[c] += a[b]
    a[b] = 0
    print(ans)

Submission status: Accepted

Solution code:
from collections import Counter 

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

dic = Counter(As)

rlt = 0
for k in dic:
  rlt += k*dic[k]

for _ in range(Q):
  b,c = map(int, input().split())
  rlt += (c-b)*dic[b]
  dic[c] += dic[b]
  dic[b] = 0
  print(rlt)

Submission status: Accepted

Solution code:
from collections import Counter
n = int(input())
a = list(map(int, input().split()))
counts = Counter(a)
q = int(input())

total = sum(a)

for i in range(q):
    b, c = map(int, input().split())
    if b < c:
        total += (c - b) * counts[b]
        counts[c] += counts[b]
        counts[b] = 0
    else:
        total -= (b - c) * counts[b]
        counts[c] += counts[b]
        counts[b] = 0
    print(total)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
q = int(input())
from collections import Counter
x = Counter(a)
r = sum(a)
for i in range(q):
    b, c = map(int, input().split())
    m = 0
    if b in x:
        m = x[b]
        x.pop(b)
        if c in x:
            x[c] += m
        else:
            x[c] = m
    r += m*(c-b)
    print(r)

Submission status: Accepted

Solution code:
import collections
n=int(input())
l=list(map(int, input().split()))
q=int(input())
s=sum(l)
d=collections.Counter(l)
for i in range(q):
    a,b=map(int, input().split())
    s=s-(a*d[a])
    s=s+(b*d[a])
    d[b]=d[b]+d[a]
    d[a]=0
    print(s)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int, input().split()))
q=int(input())
num=[0]*(10**5)
tot=0
for i in range(n):
    num[a[i]-1]+=1
    tot+=a[i]

for _ in range(q):
    b,c=map(int, input().split())
    tot+=(num[b-1]*(c-b))
    num[c-1]+=num[b-1]
    num[b-1]=0
    print(tot)

Submission status: Accepted

Solution code:
def MI():
    return map(int, input().split())

def LI():
    return list(map(int, input().split()))

# N = int(input())
# group = 0
# tmp = 0

# while tmp < N: 
#     tmp += 26**group
#     group += 1
    
# print(group)

from collections import Counter

N = int(input())
A = LI()
ans = sum(A)
Q = int(input())
A_c = Counter(A)

for _ in range(Q):
    B, C = MI()
    tmp_B = A_c[B]
    tmp_C = A_c[C]
    A_c[B] = 0
    
    if B in A_c.keys():
        A_c[C] += tmp_B
    else:
        A_c[C] = tmp_B
    
    ans = ans - B * tmp_B + C * (A_c[C] - tmp_C)
    print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = [int(e) for e in input().split()]

d = {}
sum = 0
for e in a:
    sum += e
    if e in d:
        d[e] += 1
    else:
        d[e] = 1


q = int(input())
for i in range(q):
    b, c = [int(e) for e in input().split()]

    if b in d:
        i = d.pop(b)
        if c in d:
            d[c] += i
        else:
            d[c] = i
        sum += (c - b) * i
    
    print(sum)

Submission status: Accepted

Solution code:
n=int(input())
a=[int(j)for j in input().split()]
s=sum(a)
import collections
c=collections.Counter(a)
q=int(input())
for i in range(q):
    x,y=map(int,input().split())
    s+=c[x]*(y-x)
    c[y]+=c[x]
    c[x]=0
    print(s)