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):
n = int(input())
a = list(map(int, input().split()))
q = int(input())
l = [0]*100010
ans = sum(a)

for i in a:
    l[i] += 1

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

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
q = int(input())
x = [0] * 100001
ans = sum(a)

for ai in a:
    x[ai] += 1  

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

Solution (Python):
N = int(input())
A = [int(x) for x in input().split()]

cnt = [0 for _ in range(10**5 * 5)]
for a in A:
    cnt[a] += 1

ans = sum(A)

Q = int(input())
for _ in range(Q):
    B, C = map(int, input().split())

    ans -= B * cnt[B]
    ans += C * cnt[B]

    cnt[C] += cnt[B]
    cnt[B] = 0

    print(ans)

Solution (Python):
n = int(input())
a = list(map(int,input().split()))
a_list = [0 for i in range(10**5)]
q = int(input())
sum_n = 0
ans = []

for num in a:
    a_list[num-1] += 1

for i in range(len(a_list)):
    sum_n += (i+1)*a_list[i]

for i in range(q):
    b, c = map(int,input().split())
    sum_n -= b*a_list[b-1]
    sum_n += c*a_list[b-1]
    a_list[c-1] += a_list[b-1]
    a_list[b-1] = 0
    ans.append(sum_n)

for num in ans:
    print(num)

Solution (Python):
import bisect
n = int(input())
a = list(map(int,input().split()))
q = int(input())
b = [0 for _ in range(q)]
c = [0 for _ in range(q)]
for i in range(q):
    b[i],c[i] = map(int,input().split())

cnt = [0 for _ in range(100001)]
for i in a:
    cnt[i] += 1

ans = sum(a)

for i in range(q):
    current = cnt[b[i]]*(c[i]-b[i])
    ans += current
    print(ans)
    cnt[c[i]] += cnt[b[i]]
    cnt[b[i]] = 0

Solution (Python):



from collections import Counter

def main():
    N = int(input())
    A = list(map(int, input().split()))
    ret = sum(A)
    A = Counter(A)

    dic = {}
    for i,v in A.items():
        dic[i]=v
    Q = int(input())
    for q in range(Q):
        b , c = map(int, input().split())
        x = dic.get(b,0)
        dic[c] = dic.get(c,0)+x
        dic[b] = 0
        ret += c*x-b*x

        print(ret)

if __name__ == '__main__':
    main()

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

num_count = [0]*(10**5+1)
tmp_sum = sum(A)
for i in A:
    num_count[i] += 1

for q in range(int(input())):
    B,C = map(int,input().split())
    gain = C*(num_count[B])
    loss = B*(num_count[B])
    num_count[C] += num_count[B]
    num_count[B] = 0
    tmp_sum = tmp_sum + gain - loss
    print(tmp_sum)

Solution (Python):
n=int(input())
A=list(map(int,input().split()))
q=int(input())
from collections import Counter
C=Counter(A)

ans=sum(A)
for i in range(q):
  a,b=map(int,input().split())
  ans+=(b-a) * C[a]
  C[b]+=C[a] ; C[a]=0
  print(ans)

Solution (Python):
import sys
import collections

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

tin=lambda : map(int, input().split())
lin=lambda : list(tin())
mod=1000000007



def main():
	n = int(input())
	
	
	al = lin()
	cal = collections.Counter(al)
	q = int(input())
	s = sum(al)
	for _ in range(q):
		b, c = tin()
		if b in cal:
			s += (c-b)*cal[b]
			if c in cal:
				cal[c] += cal[b]
			else:
				cal[c] = cal[b]
			cal[b]=0
			
		else:
			pass
		
		print(s)
		
		
		
		
		
		
	

isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		
			
	ret = main()
	if ret is not None:
		print(ret)

Solution (Python):

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


array = [0]*(10**5+1)
total = sum(A)

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

for bc in BC:
    b, c = bc
    total += c*array[b]-b*array[b]
    array[c] += array[b]
    array[b] = 0
    print(total)

Solution (Python):

import sys
from collections import Counter
sys.setrecursionlimit(10**8)
INF = float("inf")


class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


def main():
    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())
    
    

    group = [None]*(10**5+1)
    uf = UnionFind(N)

    
    
    
    

    for i, a in enumerate(A):
        
        
        
        if group[a] is None:
            group[a] = i
        else:
            uf.union(i, group[a])
            group[a] = uf.find(i)
    
    
    

    tot = sum(A)
    for i in range(Q):
        if group[B[i]] is None:
            b = 0
        elif group[C[i]] is None:
            b = uf.size(group[B[i]])
            group[C[i]] = uf.find(group[B[i]])
            group[B[i]] = None
        else:
            b = uf.size(group[B[i]])
            uf.union(group[B[i]], group[C[i]])
            group[C[i]] = uf.find(group[B[i]])
            group[B[i]] = None
        tot = tot - B[i]*b + C[i]*b
        print(tot)
        
        

    return


if __name__ == '__main__':
    main()

Solution (Python):
_,a,_,*q=[map(int,t.split())for t in open(0)]
s,*d=[0]*8**6
for i in a:s+=i;d[i]+=1
for b,c in q:s+=(c-b)*d[b];d[c]+=d[b];d[b]=0;print(s)

Solution (Python):
n = int(input())
count = {}
s = 0
a = [int(c) for c in input().split()]
for val in a:
	s += val
	if (val not in count): count[val] = 1
	else: count[val] += 1

q = int(input())
for _ in range(q):
	b, c = [int(c) for c in input().split()]
	if (b in count):
		temp = count[b]
		count.pop(b)
		s = s + c*temp - b*temp 
		if (c not in count): count[c] = temp 
		else: count[c] += temp
	print(s)

Solution (Python):


n = int(input())
cnt =[0]*1000000

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

for i in l:
    cnt[i] += 1
    
sums = sum(l)
    
m = int(input())

for i in range(m):
    a,b = map(int, input().split())
    
    diff = (b-a)*cnt[a]
    sums += diff
    print(sums)
    
    cnt[b] += cnt[a]
    cnt[a] = 0

Solution (Python):
from collections import defaultdict

N = int(raw_input())
A = map(int, raw_input().split())

lookup = defaultdict(int)
for a in A:
  lookup[a] += 1
  
cur_sum = 0
for k in lookup:
  cur_sum += k*lookup[k]
  
Q = int(raw_input())
for q in xrange(Q):
  b, c = map(int, raw_input().split())
  cur_sum -= b*lookup[b]
  cur_sum += c*lookup[b]
  
  lookup[c] += lookup[b]
  lookup[b] = 0
  
  print cur_sum

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

num = [0] * 100010
for i in A:
    num[i] += 1
s = sum(A)

for i in range(Q):
    p, n = BC[i][0], BC[i][1]
    s += (n - p) * num[p]
    num[n] += num[p]
    num[p] = 0
    print(s)

Solution (Python):
n = int(input())
a = [int(i) for i in input().split()]
q = int(input())
num = [0] * 100010
b = [0] * q
c = [0] * q
for i in range(q):
    b[i], c[i] = map(int, input().split())

for i in a:
    num[i] += 1

s = sum(a)






for i in range(q):
    s += (c[i]-b[i])*num[b[i]]
    num[c[i]] += num[b[i]]
    
    num[b[i]] = 0
    
    print(s)

Solution (Python):
from collections import Counter
N=int(input())
number=list(map(int,input().split()))
sum_number=sum(number)
Q=int(input())
number_count=Counter(number)


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

Solution (Python):
from collections import Counter
N=int(input())
number=list(map(int,input().split()))
sum_number=sum(number)
Q=int(input())
number_count=Counter(number)


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

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
from collections import defaultdict

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

n = int(readline())
a = list(map(int, readline().split()))
q = int(readline())
m = map(int, read().split())

counter = defaultdict(int)

for x in a:
    counter[x] += 1

total = sum(a)

for b, c in zip(m, m):
    total += (c-b) * counter[b]
    counter[c] += counter[b]
    counter[b] = 0
    print(total)

Solution (Python):
from collections import Counter

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

kosu = dict(Counter(a))

ans = sum(a)

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

    print(ans)

Solution (Python):
import sys
input = sys.stdin.buffer.readline
from collections import Counter
n=int(input())
*a,=map(int,input().split())
C=Counter(a)
ans=sum(a)
for _ in range(int(input())):
	b,c=map(int,input().split())
	ans+=C[b]*(c-b)
	C[c]+=C[b]
	C[b]=0
	print(ans)

Solution (Python):
from collections import Counter
n = int(input())
a = list(map(int, input().split()))
q = int(input())
counter = Counter(a)
sum_a = sum(a)

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

  print(sum_a)

Solution (Python):
N = int(input())
As = list(map(int, input().split()))
r = sum(As)
nAs = {}
for A in As:
  if A not in nAs:
    nAs[A] = 0
  nAs[A] += 1
Q = int(input())
for i in range(Q):
  B, C = map(int, input().split())
  if B not in nAs:
    print(r)
    continue
  n = nAs[B]
  if C not in nAs:
    nAs[C] = 0
  r += (C-B)*n
  nAs[B] = 0
  nAs[C] += n
  print(r)

Solution (Python):
import numpy as np
N = int(input())
A = list(map(int, input().split()))
Q = int(input())

count = np.zeros(10**5+1) 
for i in range(N):
  idx = A[i]
  count[idx] += 1

total = sum(A)
for i in range(Q):
  B, C = map(int, input().split())
  count_B = count[B]	
  count[B] = 0
  count[C] += count_B	
  total = total - int(count_B*B) + int(count_B*C)
  print(total)

Solution (Python):
p105=100009
count = [0]*p105
n = int(input())
a = list(map(int,input().split()))
sum=0
for i in range(n):
    count[a[i]]+=1
    sum+=a[i]

q=int(input())


for i in range(q):
    b,c=map(int,input().split())
    num=count[b]
    sum-= num*b
    sum+= num*c
    count[b] = 0
    count[c]+= num

    print(sum)

Solution (Python):
from collections import defaultdict
N = int(input())

A = [int(x) for x in input().split(" ")]
Q = int(input())
d = defaultdict(int)

ans_sum = 0
for a in A:
    d[a] += 1
    ans_sum += a

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

Solution (Python):
from collections import *

N = int(input())
A = list(map(int, input().split()))
ans = sum(A)
cnt = Counter(A)

for i in range(int(input())):
    B, C = list(map(int, input().split()))
    ans -= B * cnt[B]
    ans += C * cnt[B]
    cnt[C] += cnt[B]
    cnt[B] = 0
    print(ans)

Solution (Python):
from collections import Counter

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

cntA = Counter(A)

ans = sum(A)

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

    ans += cntA[B]*(C - B)
    cntA[C] += cntA[B]
    cntA[B] = 0
    
    print(ans)

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

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

Solution (Python):
from collections import Counter

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

counter = Counter(a)
sum_res = sum(a)

for _ in range(q):
  b, c = map(int, input().split())

  sum_res += (c - b) * counter[b]

  counter[c] += counter[b]
  counter[b] =0

  print(sum_res)

Solution (Python):
import collections

N = int(input())
a = list(map(int,input().split()))
Q = int(input())
ans = sum(a)
a = collections.Counter(a)

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

Solution (Python):

import math
import heapq, bisect
import sys
from collections import deque, defaultdict
from fractions import Fraction

mod = 10 ** 9 + 7
mod1 = 998244353


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")



class TreeNode:
    def __init__(self, k, v):
        self.key = k
        self.value = v
        self.left = None
        self.right = None
        self.parent = None
        self.height = 1
        self.num_left = 1
        self.num_total = 1


class AvlTree:

    def __init__(self):
        self._tree = None

    def add(self, k, v):
        if not self._tree:
            self._tree = TreeNode(k, v)
            return
        node = self._add(k, v)
        if node:
            self._rebalance(node)

    def _add(self, k, v):
        node = self._tree
        while node:
            if k < node.key:
                if node.left:
                    node = node.left
                else:
                    node.left = TreeNode(k, v)
                    node.left.parent = node
                    return node.left
            elif node.key < k:
                if node.right:
                    node = node.right
                else:
                    node.right = TreeNode(k, v)
                    node.right.parent = node
                    return node.right
            else:
                node.value = v
                return

    @staticmethod
    def get_height(x):
        return x.height if x else 0

    @staticmethod
    def get_num_total(x):
        return x.num_total if x else 0

    def _rebalance(self, node):

        n = node
        while n:
            lh = self.get_height(n.left)
            rh = self.get_height(n.right)
            n.height = max(lh, rh) + 1
            balance_factor = lh - rh
            n.num_total = 1 + self.get_num_total(n.left) + self.get_num_total(n.right)
            n.num_left = 1 + self.get_num_total(n.left)

            if balance_factor > 1:
                if self.get_height(n.left.left) < self.get_height(n.left.right):
                    self._rotate_left(n.left)
                self._rotate_right(n)
            elif balance_factor < -1:
                if self.get_height(n.right.right) < self.get_height(n.right.left):
                    self._rotate_right(n.right)
                self._rotate_left(n)
            else:
                n = n.parent

    def _remove_one(self, node):
        """
        Side effect!!! Changes node. Node should have exactly one child
        """
        replacement = node.left or node.right
        if node.parent:
            if AvlTree._is_left(node):
                node.parent.left = replacement
            else:
                node.parent.right = replacement
            replacement.parent = node.parent
            node.parent = None
        else:
            self._tree = replacement
            replacement.parent = None
        node.left = None
        node.right = None
        node.parent = None
        self._rebalance(replacement)

    def _remove_leaf(self, node):
        if node.parent:
            if AvlTree._is_left(node):
                node.parent.left = None
            else:
                node.parent.right = None
            self._rebalance(node.parent)
        else:
            self._tree = None
        node.parent = None
        node.left = None
        node.right = None

    def remove(self, k):
        node = self._get_node(k)
        if not node:
            return
        if AvlTree._is_leaf(node):
            self._remove_leaf(node)
            return
        if node.left and node.right:
            nxt = AvlTree._get_next(node)
            node.key = nxt.key
            node.value = nxt.value
            if self._is_leaf(nxt):
                self._remove_leaf(nxt)
            else:
                self._remove_one(nxt)
            self._rebalance(node)
        else:
            self._remove_one(node)

    def get(self, k):
        node = self._get_node(k)
        return node.value if node else -1

    def _get_node(self, k):
        if not self._tree:
            return None
        node = self._tree
        while node:
            if k < node.key:
                node = node.left
            elif node.key < k:
                node = node.right
            else:
                return node
        return None

    def get_at(self, pos):
        x = pos + 1
        node = self._tree
        while node:
            if x < node.num_left:
                node = node.left
            elif node.num_left < x:
                x -= node.num_left
                node = node.right
            else:
                return (node.key, node.value)
        raise IndexError("Out of ranges")

    @staticmethod
    def _is_left(node):
        return node.parent.left and node.parent.left == node

    @staticmethod
    def _is_leaf(node):
        return node.left is None and node.right is None

    def _rotate_right(self, node):
        if not node.parent:
            self._tree = node.left
            node.left.parent = None
        elif AvlTree._is_left(node):
            node.parent.left = node.left
            node.left.parent = node.parent
        else:
            node.parent.right = node.left
            node.left.parent = node.parent
        bk = node.left.right
        node.left.right = node
        node.parent = node.left
        node.left = bk
        if bk:
            bk.parent = node
        node.height = max(self.get_height(node.left), self.get_height(node.right)) + 1
        node.num_total = 1 + self.get_num_total(node.left) + self.get_num_total(node.right)
        node.num_left = 1 + self.get_num_total(node.left)

    def _rotate_left(self, node):
        if not node.parent:
            self._tree = node.right
            node.right.parent = None
        elif AvlTree._is_left(node):
            node.parent.left = node.right
            node.right.parent = node.parent
        else:
            node.parent.right = node.right
            node.right.parent = node.parent
        bk = node.right.left
        node.right.left = node
        node.parent = node.right
        node.right = bk
        if bk:
            bk.parent = node
        node.height = max(self.get_height(node.left), self.get_height(node.right)) + 1
        node.num_total = 1 + self.get_num_total(node.left) + self.get_num_total(node.right)
        node.num_left = 1 + self.get_num_total(node.left)

    @staticmethod
    def _get_next(node):
        if not node.right:
            return node.parent
        n = node.right
        while n.left:
            n = n.left
        return n
avl=AvlTree()

class SegmentTree1:
    def __init__(self, data, default='z', func=lambda a, b: min(a ,b)):
        """initialize the segment tree with data"""
        self._default = default
        self._func = func
        self._len = len(data)
        self._size = _size = 1 << (self._len - 1).bit_length()

        self.data = [default] * (2 * _size)
        self.data[_size:_size + self._len] = data
        for i in reversed(range(_size)):
            self.data[i] = func(self.data[i + i], self.data[i + i + 1])

    def __delitem__(self, idx):
        self[idx] = self._default

    def __getitem__(self, idx):
        return self.data[idx + self._size]

    def __setitem__(self, idx, value):
        idx += self._size
        self.data[idx] = value
        idx >>= 1
        while idx:
            self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
            idx >>= 1

    def __len__(self):
        return self._len

    def query(self, start, stop):
        if start == stop:
            return self.__getitem__(start)
        stop += 1
        start += self._size
        stop += self._size

        res = self._default
        while start < stop:
            if start & 1:
                res = self._func(res, self.data[start])
                start += 1
            if stop & 1:
                stop -= 1
                res = self._func(res, self.data[stop])
            start >>= 1
            stop >>= 1
        return res

    def __repr__(self):
        return "SegmentTree({0})".format(self.data)



class SegmentTree:
    def __init__(self, data, default=0, func=lambda a, b: a * a + b * b):
        """initialize the segment tree with data"""
        self._default = default
        self._func = func
        self._len = len(data)
        self._size = _size = 1 << (self._len - 1).bit_length()

        self.data = [default] * (2 * _size)
        self.data[_size:_size + self._len] = data
        for i in reversed(range(_size)):
            self.data[i] = func(self.data[i + i], self.data[i + i + 1])

    def __delitem__(self, idx):
        self[idx] = self._default

    def __getitem__(self, idx):
        return self.data[idx + self._size]

    def __setitem__(self, idx, value):
        idx += self._size
        self.data[idx] = value
        idx >>= 1
        while idx:
            self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
            idx >>= 1

    def __len__(self):
        return self._len

    def query(self, start, stop):
        if start == stop:
            return self.__getitem__(start)
        stop += 1
        start += self._size
        stop += self._size

        res = self._default
        while start < stop:
            if start & 1:
                res = self._func(res, self.data[start])
                start += 1
            if stop & 1:
                stop -= 1
                res = self._func(res, self.data[stop])
            start >>= 1
            stop >>= 1
        return res

    def __repr__(self):
        return "SegmentTree({0})".format(self.data)



class Factorial:
    def __init__(self, MOD):
        self.MOD = MOD
        self.factorials = [1, 1]
        self.invModulos = [0, 1]
        self.invFactorial_ = [1, 1]

    def calc(self, n):
        if n <= -1:
            print("Invalid argument to calculate n!")
            print("n must be non-negative value. But the argument was " + str(n))
            exit()
        if n < len(self.factorials):
            return self.factorials[n]
        nextArr = [0] * (n + 1 - len(self.factorials))
        initialI = len(self.factorials)
        prev = self.factorials[-1]
        m = self.MOD
        for i in range(initialI, n + 1):
            prev = nextArr[i - initialI] = prev * i % m
        self.factorials += nextArr
        return self.factorials[n]

    def inv(self, n):
        if n <= -1:
            print("Invalid argument to calculate n^(-1)")
            print("n must be non-negative value. But the argument was " + str(n))
            exit()
        p = self.MOD
        pi = n % p
        if pi < len(self.invModulos):
            return self.invModulos[pi]
        nextArr = [0] * (n + 1 - len(self.invModulos))
        initialI = len(self.invModulos)
        for i in range(initialI, min(p, n + 1)):
            next = -self.invModulos[p % i] * (p // i) % p
            self.invModulos.append(next)
        return self.invModulos[pi]

    def invFactorial(self, n):
        if n <= -1:
            print("Invalid argument to calculate (n^(-1))!")
            print("n must be non-negative value. But the argument was " + str(n))
            exit()
        if n < len(self.invFactorial_):
            return self.invFactorial_[n]
        self.inv(n)  
        nextArr = [0] * (n + 1 - len(self.invFactorial_))
        initialI = len(self.invFactorial_)
        prev = self.invFactorial_[-1]
        p = self.MOD
        for i in range(initialI, n + 1):
            prev = nextArr[i - initialI] = (prev * self.invModulos[i % p]) % p
        self.invFactorial_ += nextArr
        return self.invFactorial_[n]


class Combination:
    def __init__(self, MOD):
        self.MOD = MOD
        self.factorial = Factorial(MOD)

    def ncr(self, n, k):
        if k < 0 or n < k:
            return 0
        k = min(k, n - k)
        f = self.factorial
        return f.calc(n) * f.invFactorial(max(n - k, k)) * f.invFactorial(min(k, n - k)) % self.MOD



def powm(a, n, m):
    if a == 1 or n == 0:
        return 1
    if n % 2 == 0:
        s = powm(a, n // 2, m)
        return s * s % m
    else:
        return a * powm(a, n - 1, m) % m



def sort_list(list1, list2):
    zipped_pairs = zip(list2, list1)

    z = [x for _, x in sorted(zipped_pairs)]

    return z



def product(l):
    por = 1
    for i in range(len(l)):
        por *= l[i]
    return por



def binarySearchCount(arr, n, key):
    left = 0
    right = n - 1

    count = 0

    while (left <= right):
        mid = int((right + left)/ 2)

        
        
        if (arr[mid]<=key):
            count = mid+1
            left = mid + 1

        
        else:
            right = mid - 1

    return count



def countdig(n):
    c = 0
    while (n > 0):
        n //= 10
        c += 1
    return c


def countGreater( arr,n, k):
    l = 0
    r = n - 1

    
    
    leftGreater = n

    
    while (l <= r):
        m = int(l + (r - l) / 2)
        if (arr[m] >= k):
            leftGreater = m
            r = m - 1

        
        
        else:
            l = m + 1

    
    
    return (n - leftGreater)



n=int(input())
l=list(map(int,input().split()))
d=defaultdict(int)
for i in range(n):
    d[l[i]]+=1
s=sum(l)
for i in range(int(input())):
    b,c=map(int,input().split())
    s+=d[b]*c-d[b]*b
    print(s)
    d[c]+=d[b]
    d[b]=0

Solution (Python):
from collections import Counter

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

ans = sum(A)

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

Solution (Python):
def Replacing():
    import sys
    input = sys.stdin.readline

    n = int(input())
    A = list(map(int,input().split()))
    q = int(input())
    
    total = sum(A) 
    
    l = [0 for i in range(10**5+1)] 
    for _ in A: 
        l[_] += 1
    
    for i in range(q):
        b, c = map(int,input().split())
        total += c * l[b] 
        total -= b * l[b] 
        print(total)
        l[c] += l[b] 
        l[b] = 0 

Replacing()

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

total = sum(A) 

l = [0 for i in range(10**5+1)] 
for _ in A: 
    l[_] += 1

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