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

Solution (Python):
def solve(n, a_list, q, bc_list):
    v_list = [0] * (10 ** 5 + 1)
    s = 0
    for i in range(n):
        a = a_list[i]
        v_list[a] += 1
        s += a
    res_list = []
    for i in range(q):
        b, c = bc_list[i]
        s += v_list[b] * (c - b)
        v_list[c] += v_list[b]
        v_list[b] = 0
        res_list.append(s)
    return res_list


def main():
    n = int(input())
    a_list = list(map(int, input().split()))
    q = int(input())
    bc_list = [list(map(int, input().split())) for _ in range(q)]
    res = solve(n, a_list, q, bc_list)
    for r in res:
        print(r)


def test():
    assert solve(4, [1, 2, 3, 4], 3, [[1, 2], [3, 4], [2, 4]]) == [11, 12, 16]
    assert solve(4, [1, 1, 1, 1], 3, [[1, 2], [2, 1], [3, 5]]) == [8, 4, 4]
    assert solve(2, [1, 2], 3, [[1, 100], [2, 100], [100, 1000]]) == [102, 200, 2000]


if __name__ == "__main__":
    test()
    main()

Solution (Python):
n=int(input())
a=list(map(int, input().split()))
q=int(input())
f=[0]*(100001)
s=0
for i in a:
    f[i]+=1
    s+=i
for _ in range(q):
    b,c=map(int, input().split())
    s-=f[b]*b
    f[c]+=f[b]
    s+=c*f[b]
    f[b]=0
    print(s)

Solution (Python):

import sys

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

C = [0 for _ in range(10**5+10)]

for a in A:
    C[a] += 1
Q = int(input())

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

Solution (Python):
n=int(input())
a=list(map(int,input().split()))
s=sum(a)
q=int(input())
from collections import Counter
d=Counter(a)
for b,c in [list(map(int,input().split()))for _ in range(q)]:
  bb,cc=d[b]*b,d[b]*c
  s+=cc-bb
  d[c]+=d[b]
  d[b]=0
  print(s)

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

cnt = [0 for _ in range(101010)]

ans = 0
for x in a:
    cnt[x] += 1
    ans += x

q = int(input())

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

Solution (Python):

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

T = [0] * (10**5+1)
for a in A:
    T[a] += 1
S = sum(A)
for i in range(Q):
    b, c = map(int,input().split())
    cnt = T[b]
    T[c] += T[b]
    S -= cnt*b
    S += cnt*c
    T[b] = 0
    print(S)

Solution (Python):
import collections

n=int(input())
arr=list(map(int,input().split()))
cnt=collections.defaultdict(int)
for val in arr:
  cnt[val]+=1
sums=sum(arr)
q=int(input())
for _ in range(q):
  b,c=map(int,input().split())
  diff=(c-b)*(cnt[b])
  sums+=diff
  print(sums)
  cnt[c]+=cnt[b]
  cnt[b]=0

Solution (Python):
import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))



def read_a_int(): return int(read())


def read_ints(): return list(map(int, read().split()))


def read_col(H):
    '''H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) 
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return tuple(map(list, zip(*ret)))


def read_tuple(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


def read_matrix(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return ret
    


MOD = 10**9 + 7
INF = 2**31  

from collections import defaultdict, Counter, deque
from operator import itemgetter
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  
from math import gcd

N = read_a_int()
A = read_ints()
Q = read_a_int()
B, C = read_col(Q)


cnt = Counter(A)
ans = []
tmp = sum(A)
for b, c in zip(B, C):
    
    n = cnt[b]
    cnt[b] = 0
    
    cnt[c] += n
    tmp -= n * b
    tmp += n * c
    ans.append(tmp)





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

Solution (Python):

from collections import defaultdict
n = int(input())
mp = defaultdict(int)
arr = list(map(int, input().split()))
cur_sum = 0
for i in arr:
    cur_sum += i
    mp[i] += 1
for i in range(int(input())):
    a, b = map(int, input().split())
    fra = mp[a]
    cur_sum -= a*fra
    mp[a] -= fra
    mp[b] += fra
    cur_sum += b*fra
    print(cur_sum)

Solution (Python):
n=int(input())
a=list(map(int,input().split()))
q=int(input())
l=[0]*10**6
s=sum(a)
for i in range(n):
    l[a[i]]+=1
for i in range(q):
    b,c=map(int,input().split())
    s+=(c-b)*l[b]
    l[c]+=l[b]
    l[b]=0
    print(s)

Solution (Python):
import os
import sys
from io import BytesIO, IOBase

BUFSIZE = 8192
class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)
class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")
sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
INF = 10 ** 18
MOD = 10**9+7


Ri = lambda : [int(x) for x in sys.stdin.readline().split()]
ri = lambda : sys.stdin.readline().strip()

n = int(ri())
a = Ri()

m = int(ri())
summ = sum(a)
dic = {}
for i in a:
    dic[i] = dic.get(i,0 )+1

for _ in range(m):
    l,r = Ri()
    if l in dic:
        cnt = dic[l]
        summ -= cnt*l
        summ += cnt*r

        dic.pop(l)
        dic[r] = dic.get(r, 0) + cnt
    print(summ)

Solution (Python):
from collections import Counter

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

freq = Counter(A)
total = sum(A)
for B, C in BC:
    total += (C - B) * freq[B]
    freq[C] += freq[B]
    del freq[B]
    print(total)

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

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from itertools import accumulate, permutations, combinations, product, groupby, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
A = LIST()
Q = INT()

dic = Counter(A)
su = sum(A)
ans = []
for _ in range(Q):
    B, C = MAP()
    su -= dic[B]*B
    su += dic[B]*C
    dic[C] += dic[B]
    dic[B] = 0
    ans.append(su)
print(*ans, sep="\n")

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

Solution (Python):
def solve():
    ret = sum(A)
    dict_A = {}
    for a in A:
        dict_A[a] = dict_A.get(a, 0) + 1
    for i in range(Q):
        tmp = dict_A.get(B[i], 0)
        ret -= tmp * B[i]
        dict_A[B[i]] = 0
        dict_A[C[i]] = dict_A.get(C[i], 0) + tmp
        ret += C[i] * tmp
        print(ret)

if __name__ == "__main__":
    N = int(input())
    A = list(map(int, input().split()))
    Q = int(input())
    B, C = [], []
    for _ in range(Q):
        b, c = map(int, input().split())
        B.append(b)
        C.append(c)
    solve()

Solution (Python):
import sys

readline = sys.stdin.readline
readall = sys.stdin.read
ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))
prn = lambda x: print(*x, sep='\n')

def solve():
    n = ni()
    a = nl()
    m = 10**5 + 5
    l = [0]*m
    s = 0
    for x in a:
        l[x] += 1
        s += x
    q = ni()
    for _ in range(q):
        b, c = nm()
        v = l[b]
        s += (c - b)*v
        l[b] = 0
        l[c] += v
        print(s)
    return

solve()

Solution (Python):
from collections import Counter

n = int(input())
ns = list(map(int, input().split()))
C = Counter(ns)
s = sum(key * value for key, value in C.items())
q = int(input())
for i in range(q):
    b, c = map(int, input().split())
    s += (c - b) * C[b]
    C[c] += C[b]
    C[b] = 0
    print(s)

Solution (Python):
import sys
from collections import defaultdict, deque
import math








input = sys.stdin.readline

getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = 10 ** 20
MOD = 998244353

def solve():
    n = getN()
    nums = getList()
    d = defaultdict(int)
    for num in nums:
        d[num] += 1
    ans = sum(nums)
    
    Q = getN()
    for i in range(Q):
        b, c = getList()
        if b in d and d[b] > 0:
            ans -= b * d[b]
            ans += c * d[b]
            d[c] += d[b]
            d[b] = 0

        print(ans)



def main():
    n = getN()
    for _ in range(n):
        solve()


if __name__ == "__main__":
    
    solve()

Solution (Python):
import collections
N = int(input())
A = list(map(int, input().split()))
Q = int(input())
BC = [tuple(map(int, input().split())) for i in range(Q)]

d = collections.defaultdict(int)

S = sum(A)

for x in A:
    d[x] += 1

for B, C in BC:
    diff = C - B
    S += d[B]*diff
    d[C] += d[B]
    d[B] = 0
    print(S)

Solution (Python):
N=int(input())
a_list=list(map(int,input().split()))
Q=int(input())

N_list=[0]*(100001)
sumn=0

for a in a_list:
    N_list[a]+=1
    sumn+=a


for i in range(Q):
    b,c=map(int,input().split())
    henka=(c-b)*N_list[b]

    sumn+=henka

    N_list[c]+=N_list[b]
    N_list[b]=0

    print(sumn)

Solution (Python):


N = int(input())
dict_number = {}
S = 0

for a in map(int, input().split()):
  S += a
  if a in dict_number.keys():
    dict_number[a] += 1
  else:
    dict_number[a] = 1

Q = int(input())
for _ in range(Q):
  B,C = map(int, input().split())
  if B in dict_number.keys():
    b = dict_number.pop(B)
    S += b*(C-B)
    if C in dict_number.keys():
      dict_number[C] += b
    else:
      dict_number[C] = b
  print(S)

Solution (Python):
from collections import Counter
input()
d = Counter(map(int, input().split()))
now = sum(k * v for k, v in d.items())
for _ in range(int(input())):
    b, c = map(int, input().split())
    cnt = d[b]
    d[b] = 0
    d[c] += cnt
    now += (c - b) * cnt
    print(now)

Solution (Python):
import bisect
import collections
import copy
import functools
import heapq
import math
import sys
from collections import deque
from collections import defaultdict
input = sys.stdin.readline
sys.setrecursionlimit(10**9)
MOD = 10**9+7

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

S = sum(A)

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

Solution (Python):
from collections import defaultdict
N = int(input())
A = list(map(int,input().split()))
ans = sum(A)
d = defaultdict(lambda:0)
for i in range(N):
    d[A[i]] += 1

Q = int(input())
BC = [list(map(int,input().split())) for _ in range(Q)]

for i in range(Q):
    b,c = BC[i]
    ans += d[b]*(c-b)
    d[c] += d[b]
    d[b] = 0
    print(ans)

Solution (Python):
from collections import Counter
n = int(input())
a = [int(i) for i in input().split()]
cnt = Counter(a)
q = int(input())
sum_c = sum([i * j for i, j in cnt.items()])
for _ in range(q):
    b, c = map(int, input().split())
    sum_c += cnt[b] * (c - b)
    cnt[c] = cnt[c] + cnt[b]
    cnt[b] = 0
    print(sum_c)

Solution (Python):

import bisect
import collections
import sys

sys.setrecursionlimit(1000000)
ACMOD = 1000000007
INF = 1 << 62


def solve(N: int, A: "List[int]", Q: int, B: "List[int]", C: "List[int]"):
    _sum = sum(A)
    ac = collections.Counter(A)
    for i in range(Q):
        b, c = B[i], C[i]

        diff = ac[b] * (c - b)
        _sum += diff
        ac[c] += ac[b]
        ac[b] = 0
        print(_sum)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word

    tokens = iterate_tokens()
    N = int(next(tokens))  
    A = [int(next(tokens)) for _ in range(N)]  
    Q = int(next(tokens))  
    B = [int()] * (Q)  
    C = [int()] * (Q)  
    for i in range(Q):
        B[i] = int(next(tokens))
        C[i] = int(next(tokens))
    solve(N, A, Q, B, C)


if __name__ == '__main__':
    main()

Solution (Python):
from collections import defaultdict
d = defaultdict(int)


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


for i in range(N):
    d[A[i]] += 1
    

SUM = sum(A)


for i in range(Q):
    B,C = map(int,input().split())
    
    plus = d[B] * (C-B)
    d[C] += d[B]
    d[B] = 0
    
    SUM += plus
    print(SUM)

Solution (Python):
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())
    
cnt = [0]*(10**5+3)
for i in A:
    cnt[i]+=1
ans = sum(A)
for i in range(Q):
    ans += (C[i]-B[i])*cnt[B[i]]
    print(ans)
    cnt[C[i]] += cnt[B[i]]
    cnt[B[i]] = 0

Solution (Python):
import sys
from functools import lru_cache, cmp_to_key
from heapq import merge, heapify, heappop, heappush
from math import *
from collections import defaultdict as dd, deque, Counter as C
from itertools import combinations as comb, permutations as perm
from bisect import bisect_left as bl, bisect_right as br, bisect
from time import perf_counter
from fractions import Fraction

sys.setrecursionlimit(int(pow(10,6)))


mod = int(pow(10, 9) + 7)
mod2 = 998244353
def data(): return sys.stdin.readline().strip()
def out(*var, end="\n"): sys.stdout.write(' '.join(map(str, var))+end)
def l(): return list(sp())
def sl(): return list(ssp())
def sp(): return map(int, data().split())
def ssp(): return map(str, data().split())
def l1d(n, val=0): return [val for i in range(n)]
def l2d(n, m, val=0): return [l1d(n, val) for j in range(m)]


n=l()[0]
A=l()
d=[0 for i in range(10**5+1)]
s=0
for i in range(n):
    d[A[i]]+=1
    s+=A[i]
q=l()[0]
for i in range(q):
    b,c=l()
    s+=(c-b)*d[b]
    print(s)
    d[c]+=d[b]
    d[b]=0

Solution (Python):

import sys
from collections import defaultdict, Counter

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

"""
dicで各要素の数を保持
"""
N = ir()
A = lr()
Q = ir()
counter = Counter(A)
dic = defaultdict(int)
for k, v in counter.items():
    dic[k] = v

total = sum(A)
answer = []
for _ in range(Q):
    b, c = lr()
    num = dic[b]
    total -= num * b
    total += c * num
    dic[b] = 0
    dic[c] += num
    answer.append(total)

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

Solution (Python):

from collections import defaultdict
from typing import DefaultDict

from collections import defaultdict

N = int(input())
A = [int(i) for i in input().split()]
di_A = defaultdict(int)

for a in A:
    di_A[a] += 1

Q = int(input())
now_sum = sum(A)
ans = []
for _ in range(Q):
    b, c = [int(i) for i in input().split()]
    cnt = di_A[b]
    now_sum += cnt * (c-b) 
    di_A[b] = 0
    di_A[c] += cnt
    ans.append(now_sum)

for a in ans:
    print(a)

Solution (Python):
N = int(input())
A = list(map(int,input().split()))
S = [0]*(10**5)
ans = 0
for a in A:
    S[a-1] += 1
    ans += a
Q = int(input())
for i in range(Q):
    B,C = map(int,input().split())
    b = S[B-1]
    S[B-1] = 0
    S[C-1] += b
    ans += b*(C-B)
    print(ans)

Solution (Python):
from collections import Counter

def main():
    n = int(input())
    a = tuple([int(t)for t in input().split()])
    s = sum(a)

    c = Counter(a)

    ans = []
    q = int(input())
    for _ in range(q):
        x,y = tuple([int(t)for t in input().split()])
        s += (y-x)*c[x]
        ans.append(s)
        c[y] += c[x]
        c[x] = 0

    for a_i in ans:
        print(a_i)

if __name__ == "__main__":
    main()

Solution (Python):
import sys

sys.setrecursionlimit(1000000)

import bisect
import math
import collections
import heapq


def solve(N, As, Q, BCs):
    
    counter = collections.Counter(As)
    current_sum = sum(As)
    ans = []
    for b, c in BCs:
        if b in counter:
            original = counter[b] * b
            to = counter[b] * c
            diff = to - original
            current_sum += diff
            if c not in counter:
                counter[c] = 0
            counter[c] += counter[b]
            del counter[b]
        ans.append(str(current_sum))
    return "\n".join(ans)




if __name__ == "__main__":
    N = int(input())
    As = list(map(int, input().split(" ")))

    Q = int(input())
    BCs = [tuple(map(int, input().split(" "))) for _ in range(Q)]

    print(solve(N, As, Q, BCs))

Solution (Python):

from __future__ import division, print_function

import os
import sys
from collections import Counter
from io import BytesIO, IOBase

if sys.version_info[0] < 3:
    from __builtin__ import xrange as range
    from future_builtins import ascii, filter, hex, map, oct, zip


def main():
    n = int(input())
    a = [int(ai) for ai in input().split()]
    ca = Counter(a)

    s = sum(a)

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




BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


def print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


if sys.version_info[0] < 3:
    sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
else:
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)

input = lambda: sys.stdin.readline().rstrip("\r\n")



if __name__ == "__main__":
    main()

Solution (Python):
n=int(input())

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

ans = sum(t)

memo = [0]*100001

for i in t:
    memo[i] += 1

s=int(input())
for _ in range(s):
    b, c = (int(x) for x in input().split())
    ans += (c-b)*memo[b]
    print(ans)
    memo[c] += memo[b]
    memo[b] = 0

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

bc=[map(int,input().split()) for _ in range(q)]
b,c=[list(i) for i in zip(*bc)]
a.sort
count=[0 for _ in range(1000000)]
sum=0
for i in range(n):
  count[a[i]]=count[a[i]]+1
  sum=sum+a[i]
for i in range(q):
  sum=sum+(c[i]-b[i])*count[b[i]]
  print(sum)
  count[c[i]]=count[c[i]]+count[b[i]]
  count[b[i]]=0

Solution (Python):
import sys 
from collections import defaultdict
input = lambda:sys.stdin.readline().strip()
n = int(input())
a = list(map(int,input().split()))
a_s = sum(a)
freq = defaultdict(int)
for i in a:
    freq[i]+=1
q = int(input())
while q:
    q-=1
    bi,ci = map(int,input().split())
    new_a_s = a_s+freq[bi]*(ci-bi)
    print(new_a_s)
    freq[ci]+=freq[bi]
    freq[bi]=0
    a_s = new_a_s

Solution (Python):
import sys
INF = 1 << 60
MOD = 10**9 + 7 
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()
from collections import Counter
def resolve():
    n = int(input())
    C = Counter(map(int, input().split()))
    total = 0
    for key, val in C.items():
        total += key * val

    for _ in range(int(input())):
        b, c = map(int, input().split())
        k = C[b]
        total += k * (c - b)
        C[b] = 0
        C[c] += k
        print(total)
resolve()

Solution (Python):
def main():
    import sys
    input = sys.stdin.buffer.readline
    N = int(input())
    A = [int(i) for i in input().split()]
    Q = int(input())
    BC = [[int(i) for i in input().split()] for j in range(Q)]

    cA = [0]*(10**5+1)
    for a in A:
        cA[a] += 1
    sumA = sum(A)
    for b, c in BC:
        miA = cA[b]*b
        plA = cA[b]*c
        cA[c] += cA[b]
        cA[b] = 0
        sumA -= miA
        sumA += plA
        print(sumA)


if __name__ == '__main__':
    main()

Solution (Python):





import sys
import heapq

def main():
    n = int(input())
    nums = list(map(int, sys.stdin.readline().split()))
    cntList = [0] * (10 ** 5 + 1)
    for i in range(n):
        cntList[nums[i]] += 1
    sumVal = sum(nums)
    q = int(input())
    for _ in range(q):
        b, c = map(int, sys.stdin.readline().split())
        sumVal -= cntList[b] * b
        sumVal += cntList[b] * c
        cntList[c] += cntList[b]
        cntList[b] = 0
        print(sumVal)

    return

if __name__ == "__main__":
    main()

Solution (Python):
N=int(input())
A=list(map(int,input().split()))
X=[0]*(10**5+1)
for i in range(N):
  X[A[i]]+=1
Q=int(input())
B,C=0,0
P=sum(A)
for i in range(Q):
  B,C=map(int,input().split())
  P+=(C-B)*X[B]
  X[C]+=X[B]
  X[B]=0
  print(P)

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

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

d = {}
for a in A:
    if a not in d.keys():d[a] = 0
    d[a] += 1
s = sum(A)
q = int(input())
for i in range(q):
    b,c = map(int,input().split())
    if b in d.keys():
        s += d[b]*(c-b)
        if c not in d.keys():d[c] = 0
        d[c] += d[b]
        d[b] = 0
    print(s)

Solution (Python):
import sys
sys.setrecursionlimit(10**7) 
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right

from collections import deque


from collections import Counter

from itertools import accumulate,combinations,permutations

from heapq import heapify,heappop,heappush


from functools import lru_cache

from decimal import Decimal

def input(): 
    x=sys.stdin.readline()
    return x[:-1] if x[-1]=="\n" else x
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def main():
    mod = 1000000007
    

    N = int(input())
    
    A = tuple(map(int, input().split())) 
    
    Q=int(input())
    S = tuple(tuple(map(int, input().split())) for i in range(Q)) 
    ca=Counter(A)
    tot=sum(A)
    for B,C in S:
        red=ca[B]
        ca[B]=0
        ca[C]+=red
        tot+=red*(C-B)
        print(tot)





if __name__ == "__main__":
    main()

Solution (Python):
class BIT:
    def __init__(self,n):
        self.size=n
        self.tree=[0]*-~n
    def sum(self,i):
        s=0
        while i:
            s+=self.tree[i]
            i-=i&-i
        return s
    def add(self,i,x):
        while i<=self.size:
            self.tree[i]+=x
            i+=i&-i
def main():
    n=int(input())
    bit=BIT(10**5)
    for a in map(int,input().split()):
        bit.add(a,a)
    for _ in range(int(input())):
        b,c=map(int,input().split())
        t=bit.sum(b)-bit.sum(b-1)
        bit.add(b,-t)
        bit.add(c,t//b*c)
        print(bit.sum(10**5))
main()

Solution (Python):
from math import log
def main():
    n = int(input())
    a = [int(j) for j in input().split()]
    d = [0]*100001
    for i in range(n):
        d[a[i]]+=1
    q = int(input())
    s = sum(a)
    for i in range(q):
        b,c =[int(j) for j in input().split()]
        tmp = d[b]
        d[b] = 0
        d[c] += tmp
        s += tmp*(c-b)
        print(s)

    
        
        































































if __name__ == "__main__":
    main()

Solution (Python):
from collections import Counter as ct

n = int(input())
a = list(map(int, input().split()))
s = sum(a)
a = ct(a)
q = int(input())

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

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

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
a = list(map(int, input().split()))
q = int(input())
s = sum(a)
from collections import Counter, defaultdict
tmp = Counter(a)
c = defaultdict(int)
c.update(tmp)
ans = [None]*q
for i in range(q):
    bb,cc = map(int, input().split())
    if bb in c:
        s = s + (cc-bb) * c[bb]
        v = c.pop(bb)
        c[cc] += v
    ans[i] = s
write("\n".join(map(str, ans)))

Solution (Python):
n = int(input())
A = list(map(int, input().split()))
q = int(input())
queries = []
for _ in range(q):
    b,c = map(int,input().split())
    queries.append((b,c))

all_sum = sum(A)
cnt = {}
for a in A:
    if a not in cnt:
        cnt[a] = 0
    cnt[a] += 1
    


for (b,c) in queries:
    if b in cnt:
        all_sum -= b * cnt[b]
        all_sum += c * cnt[b]
        if c not in cnt:
            cnt[c] = 0
        cnt[c] += cnt[b]
        cnt[b] = 0
    print(all_sum)

Solution (Python):
from collections import defaultdict
N = int(input())
has = defaultdict(int)
arr = list(map(int, input().split(" "))) 
ans = 0
for a in arr :
    has[a] += 1
    ans += a

Q = int(input())
for i in range(Q) :
    b, c = map(int ,input().split(" "))
    ans -= has[b]*b
    ans += has[b]*c

    has[c] += has[b]
    has[b] = 0
    print(ans)

Solution (Python):
def main():
    n = int(input())
    a = list(map(int, input().split()))
    q = int(input())
    bc = [None for _ in range(q)]
    for i in range(q):
        bc[i] = list(map(int, input().split()))

    count = [0 for i in range(100001)]
    for i in range(n):
        count[a[i]] += 1

    ans = [0 for _ in range(q+1)]
    for i in range(100001):
        ans[0] += i * count[i]
    for i in range(q):
        ans[i+1] = ans[i] - count[bc[i][0]] * bc[i][0] + count[bc[i][0]] * bc[i][1]
        count[bc[i][1]] += count[bc[i][0]]
        count[bc[i][0]] = 0

    for i in range(1, q+1):
        print(ans[i])


if __name__ == '__main__':
    main()