题目描述

源老师给你一个由 $N$ 个正整数组成的序列 $A$ : $A_{1}, A_{2}, \cdots, A_{N}$

今天他要做一种名为替换的操作，这种操作的方式如下：

• 把序列中所有数值为 $x$ 的元素都替换为 $y$

例如序列 a = [1, 2, 2, 3, 3]，当将 $2$ 替换为 $3$，序列就变为了 a = [1, 3, 3, 3, 3]

你的任务是对于每次操作以后，输出整个序列的和。

并且他觉得只做一次操作不过瘾，他需要执行 $Q$ 次操作。

输入格式

第一行输入一个整数 $N$

接下来一行输入 $N$ 个空格隔开的整数代表 $A_1,A_2,\cdots,A_N$

第三行输入一个整数 $Q$

接下来 $Q$ 行每行输入两个整数 $x,y$，意为一次替换操作。

输出格式

输出一共输出 $Q$ 行，每次操作后都需要回到整个序列的总和。

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

11
12
16

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

8
4
4

2
1 2
3
1 100
2 100
100 1000

102
200
2000

样例 1 解释

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

每次操作后，序列变为

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

样例 2 解释

注意第三次操作是将 $3$ 替换为 $5$，但序列里没有 $3$，所以这次替换操作失效。

数据范围

对于 $50\%$ 的数据满足

• $ 1 \leq N\leq 100, 1\leq Q, A_{i}, x, y \leq 10^{5} $
• $x \neq y$

对于 $100\%$ 的数据满足

• $1 \leq N, Q, A_{i}, x, y \leq 10^{5}$
• $x \neq y$