题目描述

一个仓库有 $n$ 种货物，每种货物的库存分别是 $A_1,A_2,...A_n$ 。仓库管理员发现，有一些货物的库存量登记错误了，需要进行更新，管理员会做 $Q$ 次更新，为了方便，每次他会选择把库存等于 $B_i$ 的所有货物的库存更新为 $C_i$ ，现在他想知道在每次做完更新后， $n$ 种货物的库存总和会变成多少。

输入格式

第一行输入一个整数 $n$ 。

第二行输入 $n$ 个整数 $A_1,A_2,...,A_n$ 。

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

接下来 $Q$ 行，每行输入两个整数 $B_i,C_i$ 。

输出格式

输入 $Q$ 行，每行一个答案。

输入输出样例 #1

输入 #1

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

输出 #1

11
12
16

做了 $3$ 次批量更新，更新后的库存量如下：

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

输入输出样例 #2

输入 #2

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

输出 #2

8
4
4

输入输出样例 #3

输入 #3

2
1 2
3
1 100
2 100
100 1000

输出 #3

102
200
2000

数据范围

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