替换

题目描述

你有一个由 $N$ 个正整数 $A_{1}, A_{2}, \cdots, A_{N}$ 组成的数列 $A$。

接下来,你将连续进行以下操作 $Q$ 次:

• 在第 $i$ 次操作中,将值为 $B_{i}$ 的所有元素替换为 $C_{i}$。

对于所有 $i$ $(1 \leq i \leq Q)$,请计算第 $i$ 次操作结束后数列 $A$ 的所有元素之和 $S_{i}$。

输入格式

输入按以下格式从标准输入给出:

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

输出格式

将 $Q$ 个整数 $S_{i}$ 按以下格式输出到标准输出:

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

请注意,$S_{i}$ 可能无法容纳在 $32$ 位整数中。

样例

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

11
12
16

最初,数列 $A$ 是 $1,2,3,4$。

每次操作后,数列 $A$ 变为如下:

• $2, 2, 3, 4$
• $2, 2, 4, 4$
• $4, 4, 4, 4$

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

8
4
4

请注意,数列 $A$ 中也可能一个值为 $B_{i}$ 的元素都没有。

2
1 2
3
1 100
2 100
100 1000

102
200
2000

数据范围

• 输入均为整数
• $1 \leq N, Q, A_{i}, B_{i}, C_{i} \leq 10^{5}$
• $B_{i} \neq C_{i}$