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:
n=int(input())
a=list(map(int,input().split()))
q=int(input())
sum1=sum(a)
d={}
for x in range(n):
  s=a[x]
  if s not in d:
    d[s]=0
  d[s]+=1

for y in range(q):
  h,g=map(int,input().split())
  if h in d:
    r=d[h]
    sum1=sum1-r*h
    
    if g not in d:
      d[g]=0
    d[g]+=r
    sum1+=r*g
    d[h]=0
    
  print(sum1)

Submission status: Accepted

Solution code:
from collections import Counter

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

ans = sum(a)
a_c = Counter(a)

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

Submission status: Accepted

Solution code:
n = int(input())
ls = [0 for i in range(10 ** 5)]
lsa = list(map(int,input().split()))

for i in range(len(lsa)):
    ls[lsa[i] - 1] += 1

ans1 = sum(lsa)
ansls = []

q = int(input())

for i in range(q):
    b, c = map(int,input().split())
    if i == 0:
        ans = ans1 + ((c - b) * ls[b - 1])
    else:
        ans = ansls[-1] + ((c - b) * ls[b - 1])
    ansls.append(ans)
    ls[c - 1] += ls[b - 1]
    ls[b - 1] = 0

for i in range(q):
    print(ansls[i])

Submission status: Accepted

Solution code:

def solve():
    n=int(input())
    a=list(map(int,input().split()))
    cnt=[0]*(int(1e5)+9)
    s=0
    for i in range(0,n) :
        s+=a[i]
        cnt[a[i]]+=1
    q=int(input())
    for q in range(0,q) :
        b,c=map(int,input().split())
        ct=cnt[b]
        s+=ct*(c-b)
        cnt[b]=0
        cnt[c]+=ct
        print(s)

solve()

Submission status: Accepted

Solution code:
from collections import Counter
n = int(input())
A = list(map(int, input().split()))
q = int(input())
dict_A = Counter(A)
sum_list = sum(A)
for i in range(q):
    b, c = map(int, input().split())
    if b not in dict_A:
        print(sum_list)
    else:
        b_num = dict_A[b]
        dict_A[c] += dict_A[b]
        dict_A[b] = 0
        sum_list = sum_list + (c - b) * b_num
        print(sum_list)

Submission status: Accepted

Solution code:
from collections import Counter

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

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

Submission status: Accepted

Solution code:
import collections
N = int(input())
A = list(map(int, input().split()))
Q = int(input())
query = []
for _ in range(Q):
    query.append(tuple(map(int, input().split())))

dict_A = collections.Counter(A)
# print(dict_A)
ans = sum(A)
for i in range(Q):
    if query[i][0] in dict_A.keys():
        val = dict_A.pop(query[i][0])
        if query[i][1] in dict_A.keys():
            dict_A[query[i][1]] += val
        else:
            dict_A[query[i][1]] = val
        ans = ans - (val*query[i][0]) + (val*query[i][1])
    print(ans)

Submission status: Accepted

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

nums = [0 for i in range(1,100010)]

S = sum(A)
for i in range(N):
    nums[A[i]] += 1

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

Submission status: Accepted

Solution code:
n = int(input())
a = [int(x) for x in input().split()]
q = int(input())
bc=[]
for i in range(q):
    bc.append([int(x) for x in input().split()])

a_cnt=[0]*(10**5+1)

for i in range(len(a)):
	a_cnt[a[i]]+=1

a_goukei=sum(a)

for gyou in range(q):
	a_goukei+=(bc[gyou][1]-bc[gyou][0])*a_cnt[bc[gyou][0]]
	print(a_goukei)
	a_cnt[bc[gyou][1]]+=a_cnt[bc[gyou][0]]
	a_cnt[bc[gyou][0]]=0

Submission status: Accepted

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

table = {}
sum = 0


for i in range(n):
    sum += a[i]
    if a[i] not in table.keys():
        table[a[i]] = 1
    else:
        table[a[i]] += 1
for i in range(q):
    b,c = map(int,input().split())
    if b in table.keys():
        sum -= b * table[b]
        sum += c * table[b]
        
        if c not in table.keys():
            table[c] = table[b]
        else:
            table[c] += table[b]
        table[b] = 0    
    print(sum)

Submission status: Accepted

Solution code:
import collections

n = int(input())
A = list(map(int,input().split()))
a = collections.Counter(A)
sum_ = sum(A)

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

for j,b in enumerate(B):
  sum_+=a[b]*(C[j]-b)
  a[C[j]]+=a[b]
  a[b]=0
  print(sum_)

Submission status: Accepted

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

C=[0]*(10**5+1)

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

ans=sum(A)

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)

Submission status: Accepted

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

count = [0] * 100000
for i in range(n):
    count[a[i] - 1] += 1
    
for i in range(q):
    o = list(map(int, input().split()))
    s += (o[1] - o[0]) * count[o[0] - 1]
    count[o[1] - 1] += count[o[0] - 1]
    count[o[0] - 1] = 0
    print(s)

Submission status: Accepted

Solution code:
import sys
import numpy as np
from heapq import heappush, heappop 
from bisect import bisect_left as bi_l, bisect_right as bi_r
from collections import deque, Counter, defaultdict
from itertools import combinations, product
inf = float('inf')
MOD = 10**9+7
# MOD = 998244353


class NumberTheory():
  def __init__(self, n=2*10**6, numpy=True):
    self.n = n
    self.np_flg = numpy 
    self.is_prime_number, self.prime_numbers = self.sieve_of_eratosthenes(n)
  
  def sieve_of_eratosthenes(self, n):
    if self.np_flg:
      sieve = np.ones(n+1, dtype=np.int64); sieve[:2] = 0
      for i in range(2, int(n**.5)+1):
        if sieve[i]: sieve[i*2::i] = 0
      prime_numbers = np.flatnonzero(sieve)
    else:
      sieve = [1] * (n+1); sieve[0] = sieve[1] = 0
      for i in range(2, int(n**.5)+1):
        if not sieve[i]: continue
        for j in range(i*2, n+1, i): sieve[j] = 0
      prime_numbers = [i for i in range(2, n+1) if sieve[i]]
    return sieve, prime_numbers 

  def prime_factorize(self, n):
    res = dict()
    if n < 2: return res
    border = int(n**.5)
    for p in self.prime_numbers:
      if p > border: break
      while n % p == 0: res[p] = res.get(p, 0)+1; n //= p
      if n == 1: return res
    res[n] = 1; return res

  def prime_factorize_factorial(self, n):
    res = dict()
    for i in range(2, n+1):
      for p, c in self.prime_factorize(i).items(): res[p] = res.get(p, 0)+c
    return res
  
  @staticmethod
  def gcd(a, b): return gcd(b, a%b) if b else abs(a)

  @staticmethod
  def lcm(a, b): return abs(a // gcd(a, b) * b)

  @staticmethod
  def find_divisors(n):
    divisors = []
    for i in range(1, int(n**.5)+1):
      if n%i: continue
      divisors.append(i)
      j = n // i
      if j != i: divisors.append(j)
    return divisors
  
  @staticmethod
  def base_convert(n, b):
    if not n: return [0]
    res = []
    while n:
      n, r = divmod(n, b)
      if r < 0: n += 1; r -= b
      res.append(r)
    return res


class UnionFind():
  def __init__(self, n=10**6):
    self.root = list(range(n))
    self.height = [0] * n 
    self.size = [1] * n 
  
  def find_root(self, u):
    if self.root[u] == u: return u
    self.root[u] = self.find_root(self.root[u])
    return self.root[u]
  
  def unite(self, u, v):
    ru = self.find_root(u)
    rv = self.find_root(v)
    if ru == rv: return 
    hu = self.height[ru]
    hv = self.height[rv]
    if hu >= hv:
      self.root[rv] = ru 
      self.size[ru] += self.size[rv]
      self.height[ru] = max(hu, hv+1)
    else:
      self.root[ru] = rv 
      self.size[rv] += self.size[ru]


class Combinatorics():
  def __init__(self, N=10**9, n=10**6, mod=10**9+7, numpy=True):
    self.mod = mod
    self.nCr = dict()
    self.np_flg=numpy
    self.make_mod_tables(N, n)

  sys.setrecursionlimit(10**6)
  def choose(self, n, r, mod=None): # no mod, or mod ≠ prime
    if r > n or r < 0: return 0
    if r == 0: return 1
    if (n, r) in self.nCr: return self.nCr[(n, r)]
    if not mod:
      self.nCr[(n, r)] = (self.choose(n-1, r) + self.choose(n-1, r-1))
    else:
      self.nCr[(n, r)] = (self.choose(n-1, r, mod) + self.choose(n-1, r-1, mod)) % mod
    return self.nCr[(n,r)]
  
  def cumprod(self, a):
    p = self.mod
    l = len(a); sql = int(np.sqrt(l)+1)
    a = np.resize(a, sql**2).reshape(sql, sql)
    for i in range(sql-1): a[:, i+1] *= a[:, i]; a[:, i+1] %= p
    for i in range(sql-1): a[i+1] *= a[i, -1]; a[i+1] %= p
    return np.ravel(a)[:l]

  def make_mod_tables(self, N, n):
    p = self.mod
    if self.np_flg:
      fac = np.arange(n+1); fac[0] = 1; fac = self.cumprod(fac)
      ifac = np.arange(n+1, 0, -1); ifac[0] = pow(int(fac[-1]), p-2, p)
      ifac = self.cumprod(ifac)[n::-1]
      n_choose = np.arange(N+1, N-n, -1); n_choose[0] = 1;
      n_choose[1:] = self.cumprod(n_choose[1:])*ifac[1:n+1]%p
    else:
      fac = [None]*(n+1); fac[0] = 1
      for i in range(n): fac[i+1] = fac[i]*(i+1)%p
      ifac = [None]*(n+1); ifac[n] = pow(fac[n], p-2, p)
      for i in range(n, 0, -1): ifac[i-1] = ifac[i]*i%p
      n_choose = [None] * (n+1); n_choose[0] = 1
      for i in range(n): n_choose[i+1] = n_choose[i]*(N-i)%p
      for i in range(n+1): n_choose[i] = n_choose[i]*ifac[i]%p
    self.fac, self.ifac, self.mod_n_choose = fac, ifac, n_choose


def z_algorithm(s):
  n = len(s)
  a = [0] * n; a[0] = n
  l = r = -1
  for i in range(1, n):
    if r >= i: a[i] = min(a[i-l], r-i)
    while i + a[i] < n and s[i+a[i]] == s[a[i]]: a[i] += 1
    if i+a[i] >= r: l, r = i, i+a[i]
  return a


class ABC001():
  def A():
    h1, h2 = map(int, sys.stdin.read().split())
    print(h1-h2)

  def B(): pass
  def C(): pass 
  def D(): pass 


class ABC002():
  def A():
    x, y = map(int, sys.stdin.readline().split())
    print(max(x, y))

  def B():
    vowels = set('aeiou')
    s = sys.stdin.readline().rstrip() 
    t = ''
    for c in s:
      if c in vowels: continue 
      t += c 
    print(t)

  def C():
    *coords, = map(int, sys.stdin.readline().split())
    def triangle_area(x0, y0, x1, y1, x2, y2):
      x1 -= x0; x2 -= x0; y1 -= y0; y2 -= y0;
      return abs(x1*y2 - x2*y1) / 2
    print(triangle_area(*coords))

  def D():
    n, m = map(int, sys.stdin.readline().split())
    edges = set()
    for _ in range(m):
      x, y = map(int, sys.stdin.readline().split())
      x -= 1; y -= 1
      edges.add((x, y))
    cand = []
    for i in range(1, 1<<n):
      s = [j for j in range(n) if i>>j & 1]
      for x, y in combinations(s, 2):
        if (x, y) not in edges: break
      else:
        cand.append(len(s))
    print(max(cand))


class ABC003():
  def A():
    n = int(sys.stdin.readline().rstrip())
    print((n+1)*5000)

  def B():
    atcoder = set('atcoder')
    s, t = sys.stdin.read().split()
    for i in range(len(s)):
      if s[i] == t[i]: continue
      if s[i] == '@' and t[i] in atcoder: continue 
      if t[i] == '@' and s[i] in atcoder: continue
      print('You will lose')
      return 
    print('You can win')

  def C():
    n, k, *r = map(int, sys.stdin.read().split())
    res = 0
    for x in sorted(r)[-k:]:
      res = (res+x) / 2
    print(res)

  def D(): pass 


class ABC004():
  def A():
    print(int(sys.stdin.readline().rstrip())*2)

  def B():
    c = [sys.stdin.readline().rstrip() for _ in range(4)]
    for l in c[::-1]:
      print(l[::-1])

  def C():
    n = int(sys.stdin.readline().rstrip())
    n %= 30
    res = list(range(1, 7))
    for i in range(n):
      i %= 5
      res[i], res[i+1] = res[i+1], res[i]
    print(''.join(map(str, res)))

  def D(): pass 


class ABC005():
  def A():
    x, y = map(int, sys.stdin.readline().split())
    print(y//x)

  def B():
    n, *t = map(int, sys.stdin.read().split())
    print(min(t))

  def C():
    t = int(sys.stdin.readline().rstrip())
    n = int(sys.stdin.readline().rstrip())
    a = [int(x) for x in sys.stdin.readline().split()]
    m = int(sys.stdin.readline().rstrip())
    b = [int(x) for x in sys.stdin.readline().split()]
    i = 0
    for p in b:
      if i == n: print('no'); return 
      while p-a[i] > t:
        i += 1
        if i == n: print('no'); return 
      if a[i] > p: print('no'); return 
      i += 1
    print('yes')

  def D():
    n = int(sys.stdin.readline().rstrip())
    d = np.array([sys.stdin.readline().split() for _ in range(n)], np.int64)
    s = d.cumsum(axis=0).cumsum(axis=1)
    s = np.pad(s, 1)
    max_del = np.zeros((n+1, n+1), dtype=np.int64)
    for y in range(1, n+1):
      for x in range(1, n+1):
        max_del[y, x] = np.amax(s[y:n+1, x:n+1] - s[0:n-y+1, x:n+1] - s[y:n+1, 0:n-x+1] + s[0:n-y+1, 0:n-x+1])
    res = np.arange(n**2+1)[:, None]
    i = np.arange(1, n+1)
    res = max_del[i, np.minimum(res//i, n)].max(axis=1)
    q = int(sys.stdin.readline().rstrip())
    p = np.array(sys.stdin.read().split(), dtype=np.int64)
    print(*res[p], sep='\n')


class ABC006():
  def A():
    n = sys.stdin.readline().rstrip()
    if '3' in n: print('YES')
    elif int(n)%3 == 0: print('YES')
    else: print('NO')

  def B():
    mod = 10007
    t = [0, 0, 1]
    for _ in range(1001001):
      t.append(t[-1]+t[-2]+t[-3]); t[-1] %= mod
    n = int(sys.stdin.readline().rstrip())
    print(t[n-1])
    
  def C():
    n, m = map(int, sys.stdin.readline().split())
    cnt = [0, 0, 0]
    if m == 1: cnt = [-1, -1, -1]
    else:
      if m & 1: m -= 3; cnt[1] += 1; n -= 1
      cnt[2] = m//2 - n 
      cnt[0] = n - cnt[2]
    if cnt[0]<0 or cnt[1]<0 or cnt[2]<0: print(-1, -1, -1)
    else: print(*cnt, sep=' ')
      
  def D():
    n, *c = map(int, sys.stdin.read().split())
    lis = [inf]*n 
    for x in c: lis[bi_l(lis, x)] = x 
    print(n - bi_l(lis, inf))


class ABC007():
  def A():
    n = int(sys.stdin.readline().rstrip())
    print(n-1)

  def B():
    s = sys.stdin.readline().rstrip()
    if s == 'a': print(-1)
    else: print('a')

  def C():
    r, c = map(int, sys.stdin.readline().split())
    sy, sx = map(int, sys.stdin.readline().split())
    gy, gx = map(int, sys.stdin.readline().split())
    sy -= 1; sx -=1; gy -= 1; gx -= 1
    maze = [sys.stdin.readline().rstrip() for _ in range(r)]
    queue = deque([(sy, sx)])
    dist = np.full((r, c), np.inf); dist[sy, sx] = 0
    while queue:
      y, x = queue.popleft()
      for i, j in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
        i += y; j += x
        if maze[i][j] == '#' or dist[i, j] != np.inf: continue 
        dist[i, j] = dist[y, x] + 1
        queue.append((i, j))
    print(int(dist[gy, gx]))
  
  def D(): pass 


class ABC008():
  def A():
    s, t = map(int, sys.stdin.readline().split())
    print(t-s+1)

  def B():
    n, *s = sys.stdin.read().split()
    res = defaultdict(int)
    for name in s: res[name] += 1
    print(sorted(res.items(), key=lambda x: x[1])[-1][0])

  def C():
    n, *a = map(int, sys.stdin.read().split())
    a = np.array(a)
    c = n - np.count_nonzero(a[:, None]%a, axis=1)
    print(np.sum((c+1)//2/c))
  
  def D(): pass

class ABC009():
  def A():
    n = int(sys.stdin.readline().rstrip())
    print((n+1)//2)

  def B():
    n, *a = map(int, sys.stdin.read().split())
    print(sorted(set(a))[-2])
    
  def C():
    n, k = map(int, sys.stdin.readline().split())
    s = list(sys.stdin.readline().rstrip())
    cost = [1]*n
    r = k
    for i in range(n-1):
      q = []
      for j in range(i+1, n):
        if s[j] < s[i] and cost[i]+cost[j] <= r:
          heappush(q, (s[j], cost[i]+cost[j], -j))
      if not q: continue
      _, c, j = heappop(q); j = -j 
      s[i], s[j] = s[j], s[i]
      r -= c 
      cost[i] = cost[j] = 0
    print(''.join(s))
      
  def D(): pass 


class ABC010():
  def A():
    print(sys.stdin.readline().rstrip()+'pp')
  def B():
    n, *a = map(int, sys.stdin.read().split())
    tot = 0
    for x in a:
      c = 0 
      while x%2==0 or x%3==2:
        x -= 1
        c += 1
      tot += c
    print(tot)

  def C():
    sx, sy, gx, gy, t, v, n, *xy = map(int, sys.stdin.read().split())
    x, y = np.array(xy).reshape(-1, 2).T
    def dist(x1, y1, x2, y2):
      return np.sqrt((x2-x1)**2 + (y2-y1)**2)
    ans = 'YES' if (dist(sx, sy, x, y)+dist(x, y, gx, gy) <= v*t).any() else 'NO'
    print(ans)

  def D(): pass 

class ABC011():
  def A():
    n = int(sys.stdin.readline().rstrip())
    print(n%12+1)

  def B():
    s = sys.stdin.readline().rstrip() 
    print(s[0].upper()+s[1:].lower())

  def C():
    n, *ng = map(int, sys.stdin.read().split())
    ng = set(ng)
    if n in ng: print('NO')
    else:
      r = 100
      while n > 0:
        if r == 0: print('NO'); return
        for i in range(3, 0, -1):
          if (n-i) in ng: continue 
          n -= i
          r -= 1
          break 
        else: print('NO'); return 
      print('YES')

  def D(): pass 


class ABC170():
  def A():
    x = [int(x) for x in sys.stdin.readline().split()]
    for i in range(5):
      if x[i] != i+1:
        print(i+1)
        break

  def B():
    x, y = map(int, sys.stdin.readline().split())
    print('Yes' if 2*x <= y <= 4*x and y%2 == 0 else 'No')
      
  def C():
    x, n, *p = map(int, sys.stdin.read().split())
    a = list(set(range(102)) - set(p))
    a = [(abs(y-x), y) for y in a]
    print(sorted(a)[0][1])

  def D():
    n, *a = map(int, sys.stdin.read().split())
    cand = set(a)
    cnt = 0
    for x, c in sorted(Counter(a).items()):
      cnt += c == 1 and x in cand
      cand -= set(range(x*2, 10**6+1, x))
    print(cnt)

  def E():
    n, q = map(int, sys.stdin.readline().split())
    queue = [] 
    num_kindergarten = 2*10**5
    queue_kindergarten = [[] for _ in range(num_kindergarten)]
    highest_kindergarten = [None] * num_kindergarten
    where = [None] * n
    rate = [None] * n

    def entry(i, k):
      where[i] = k
      while queue_kindergarten[k]:
        r, j = heappop(queue_kindergarten[k])
        if where[j] != k or j == i: continue 
        if rate[i] >= -r:
          highest_kindergarten[k] = rate[i]
          heappush(queue, (rate[i], k, i))
        heappush(queue_kindergarten[k], (r, j))
        break
      else:
        highest_kindergarten[k] = rate[i]
        heappush(queue, (rate[i], k, i))
      heappush(queue_kindergarten[k], (-rate[i], i))

    def transfer(i, k):
      now = where[i]
      while queue_kindergarten[now]:
        r, j = heappop(queue_kindergarten[now])
        if where[j] != now or j == i: continue
        if highest_kindergarten[now] != -r:
          highest_kindergarten[now] = -r
          heappush(queue, (-r, now, j))
        heappush(queue_kindergarten[now], (r, j))
        break
      else:
        highest_kindergarten[now] = None
      entry(i, k)

    def inquire():
      while True:
        r, k, i = heappop(queue)
        if where[i] != k or r != highest_kindergarten[k]: continue 
        heappush(queue, (r, k, i))
        return r

    for i in range(n):
      a, b = map(int, sys.stdin.readline().split())
      rate[i] = a 
      entry(i, b-1)
    for _ in range(q):
      c, d = map(int, sys.stdin.readline().split())
      transfer(c-1, d-1)
      print(inquire())
    
  def F(): pass 


class ABC171():
  def A():
    c = sys.stdin.readline().rstrip()
    print('A' if c < 'a' else 'a')

  def B():
    n, k, *p = map(int, sys.stdin.read().split())
    print(sum(sorted(p)[:k]))

  def C():
    n = int(sys.stdin.readline().rstrip())
    n -= 1
    l = 1
    while True:
      if n < pow(26, l):
        break 
      n -= pow(26, l)
      l += 1
    res = ''.join([chr(ord('a')+d%26) for d in NumberTheory.base_convert(n, 26)][::-1])
    res = 'a'*(l-len(res)) + res
    print(res)

  def D():
    n = int(sys.stdin.readline().rstrip())
    a = [int(x) for x in sys.stdin.readline().split()]
    s = sum(a)
    cnt = Counter(a)
    q = int(sys.stdin.readline().rstrip())
    for _ in range(q):
      b, c = map(int, sys.stdin.readline().split())
      s += (c-b)*cnt[b]
      print(s)
      cnt[c] += cnt[b]; cnt[b] = 0
  def E(): pass 
  def F(): pass 

if __name__ == '__main__':
  ABC171.D()

Submission status: Accepted

Solution code:
n = int(input())
a = [int(i) for i in input().split()]
q = int(input())
d = { }
s = 0
for i in a:
	if i not in d:
		d[i] = 0
	d[i] += 1
	s += i
while q:
	q -= 1
	b, c = map(int, input().split())
	if b in d:
		if c not in d:
			d[c] = 0
		s += (c - b) * d[b]
		d[c] += d[b]
		del d[b]
	print(s)

Submission status: Accepted

Solution code:
N = int(input())
a = list(map(int,input().split()))
Q = int(input())
cnt = [0]*1000001
result = 0
for i in a:
    cnt[i] += 1
    result += i
for j in range(Q):
    b,c = map(int,input().split())
    cnt[c] += cnt[b]
    n = cnt[b]
    cnt[b] = 0
    result += (c-b)*n
    print(result)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import Counter

# print('input >>')
N = input()
As = list(map(int,(input().split())))
Q = int(input())
BCs = []
for _ in range(Q):
    BCs.append(tuple(map(int,(input().split()))))

counter = dict(Counter(As))
sum_ = sum(As)

for BC in BCs:
    if not BC[0] in counter:
        counter[BC[0]] = 0
    if not BC[1] in counter:
        counter[BC[1]] = 0
    sa = BC[1] - BC[0]
    sum_ += counter[BC[0]] * sa
    counter[BC[1]] = counter[BC[1]] + counter[BC[0]]
    counter[BC[0]] = 0
    # print(counter)
    print(sum_)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
q = int(input())
xy = [map(int, input().split()) for _ in range(q)]
b, c = [list(i) for i in zip(*xy)]

ans = 0

sum_all = 0
for cnt in range(n):
    sum_all += a[cnt]

a = sorted(a)
list_a_num = [0]*(10**5 + 1)
for cnt in range(n):
    list_a_num[a[cnt]] += 1

for cnt in range(q):
    sum_all += (c[cnt] - b[cnt]) * list_a_num[b[cnt]]
    list_a_num[c[cnt]] += list_a_num[b[cnt]]
    list_a_num[b[cnt]] = 0
    print(sum_all)

Submission status: Accepted

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

N = int(input())
A = [int(i) for i in input().split()]
count = [0] * 10**5
for i in range(N):
        count[A[i]-1] += 1

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

    print(ans)

    count[C-1] += count[B-1]
    count[B-1] = 0

Submission status: Accepted

Solution code:
import collections

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

CNT = collections.Counter(A)
ANS = []
ans = sum(A)

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

for i in ANS:
    print(i)

Submission status: Accepted

Solution code:
import collections

n = int(input())
A = list(map(int, input().split()))
ans = sum(A)
ANS = []
q = int(input())
T = collections.Counter(A)
for i in range(q):
    b, c = map(int, input().split())
    t = T[b]
    ans -= t * b
    ans += t * c
    T[b] = 0
    T[c] += t
    ANS.append(ans)
for i in ANS:
    print(i)

Submission status: Accepted

Solution code:
n = int(input())
a_list = list(map(int, input().split()))
sum_a = sum(a_list)
num_a = [0]*(10**5)
for i in a_list:
    num_a[i-1] += 1
    
q = int(input())
for _ in range(q):
    b, c = list(map(int, input().split()))
    sum_a = sum_a + c * num_a[b-1] - b *num_a[b-1]
    num_a[c-1] += num_a[b-1]
    num_a[b-1] = 0
    print(sum_a)

Submission status: Accepted

Solution code:
import collections

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

x = dict(collections.Counter(A))
ans = sum(k * v for k, v in x.items())
for _ in range(Q):
    B, C = map(int, input().split())
    b = x.get(B, 0)
    c = x.get(C, 0)

    ans -= b * B
    ans += b * C

    x[C] = c + b
    x[B] = 0

    print(ans)

Submission status: Accepted

Solution code:
import collections

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

bc = []

for i in range(q):
    bci = list(map(int, input().split()))
    bc.append(bci)

d = collections.Counter(a)
ans = sum(a)

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

Submission status: Accepted

Solution code:
import collections

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

d = collections.Counter(a)
ans = sum(a)

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

Submission status: Accepted

Solution code:
from collections import Counter

n = int(input())
a = list(map(int,input().split()))
q = int(input())
freq = Counter(a)
sm = sum(a)
for i in range(q):
    b,c = map(int,input().split())
    bn = freq[b]
    freq[b] = 0
    if c in freq:
        freq[c] += bn
    else:
        freq[c] = bn
    sm = sm + (c-b)*bn
    print(sm)

Submission status: Accepted

Solution code:
n = int(input())

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

d = {}
s = 0
for i in a:
    if i in d:
        d[i] += 1
    else:
        d[i] = 1
    
    s += i

q = int(input())

for i in range(0, q):

    b, c = map(int, input().split())

    if b in d:
        s = s - (d[b] * b) + (d[b] * c)
        if c in d:
            d[c] += d[b]
        else:
            d[c] = d[b]
        d[b] = 0
    
        print(s)
    else:
        print(s)

Submission status: Accepted

Solution code:
import collections

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


for i in range(q):
    bci = list(map(int, input().split()))
    bc.append(bci)

cc = collections.Counter(a)
li = cc.most_common()
su = sum(a)

for i in range(q):
    b, c = bc[i]
    if cc[b]:
        num = (c-b)*cc[b]
    else:
        num = 0
    su += num
    print(su)
    if cc[c]:
        cc[c] += cc[b]
    else:
        cc[c] = cc[b]
    cc[b] = 0

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import Counter
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

c = Counter(a)
l = [0]*(10 ** 5 + 1)
for k, v in c.items():
    l[k] = v

sm = sum(a)

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

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 = [0]*10**5
ans = sum(a)
for i in a:
    cnt[i-1] += 1

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

Submission status: Accepted

Solution code:
def fun(d):
	cnt = 0
	for i in d:
		cnt+= i*d[i]
	return cnt

from collections import defaultdict
d = defaultdict(int)
n = int(input())
A = list(map(int,input().split()))
for i in range(n):
	d[A[i]]+=1
q = int(input())
cnt = sum(A)
for i in range(q):
	b,c = map(int,input().split())
	if b in d:
		cnt+=(-b*d[b] + c*d[b])
		d[c]+=d[b]
		d[b]=0
		#print(cnt,d)
	print(cnt)

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))
SUM=sum(A)
Q=int(input())
List=[0 for _ in range(10**5+1)]
for a in A:
    List[a]+=1
for q in range(Q):
    B,C=map(int,input().split())
    SUM-=B*List[B]
    SUM+=C*List[B]
    List[C]+=List[B]
    List[B]=0
    print(SUM)

Submission status: Accepted

Solution code:
import numpy as np
N=int(input())
A=list(map(int,input().split()))
SUM=sum(A)
Q=int(input())
List=np.array([0 for _ in range(10**5+1)])
for a in A:
    List[a]+=1
for q in range(Q):
    B,C=map(int,input().split())
    SUM-=B*List[B]
    SUM+=C*List[B]
    List[C]+=List[B]
    List[B]=0
    print(SUM)

Submission status: Accepted

Solution code:
N = int(input())
A= list(map(int,input().split()))
Q = int(input())
heavy = [0] * (10 ** 5 + 1)
for i in A:
  heavy[i] += 1
s = sum(A)
for i in range(Q):
  be,af = map(int,input().split())
  s -= be * heavy[be]
  s += af * heavy[be]
  heavy[af] += heavy[be]
  heavy[be] = 0
  print(s)

Submission status: Accepted

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

import collections
ans = sum(a)
a = collections.Counter(a)

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

Submission status: Accepted

Solution code:
from collections import Counter
from sys import stdin
N = int(stdin.readline().rstrip())
A = [int(_) for _ in stdin.readline().rstrip().split()]
CA = Counter(A)
Q = int(stdin.readline().rstrip())
ans = sum(A)
for i in range(Q):
    b, c = [int(_) for _ in stdin.readline().rstrip().split()]
    ans += (c-b)*CA[b]
    CA[c] += CA[b]
    CA[b] = 0
    print(ans)

Submission status: Accepted

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

heavy = [0] * (10 ** 5 + 1)
for x in A:
    heavy[x] += 1
suma = sum(A)

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