题目描述

超市经理小李负责管理一个有 $N$ 种商品的库存系统。每种商品都有一个库存数量，记录在一个序列 $X$ 中，序列中的元素为 $X_1, X_2, \dots, X_N$，分别表示第 $1$ 种到第 $N$ 种商品的库存量（均为正整数）。

由于市场需求的波动，小李需要定期调整某些商品的库存数量。他计划在未来 $K$ 天内，每天进行一次库存调整。具体来说：

在第 $i$ 天，小李会将库存数量为 $Y_i$ 的所有商品的库存量统一调整为 $Z_i$。每次调整后，小李希望快速知道整个库存系统中所有商品的库存总量 $S_i$，以便及时更新库存报告。

作为超市的 IT 顾问，你的挑战是设计一个程序，帮助小李在每次调整后高效地计算出新的库存总量 $S_i$。

输入格式

• 第一行：包含一个整数 $N$
• 第二行：包含 $N$ 个整数，表示 $X_1 \sim X_N$
• 第三行：包含一个整数 $K$
• 接下来 $K$ 行，每行包括两个整数，分别表示 $Y_i$ 和 $Z_i$

输出格式

输出 $K$ 行，表示每次调整后的库存总量 $S_i$。

样例

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

11
12
16

数据范围

• 对于 $10\%$ 的数据，$1 \le N, K \le 100$
• 对于 $100\%$ 的数据，$1 \le N, K, X_i, Y_i, Z_i \le 10^5$，$Y_i \ne Z_i$