题目描述

茜同学很喜欢统治世界的感觉。但好像学校里不能随便指挥人，她决定玩一些指挥数字的游戏。

她有一个长度为 $n$ 的正整数数组 $[a_1, a_2, \cdots, a_n]$，并打算指挥这些数字 $q$ 次。

第 $i$ 次指挥会将值为 $b_i$ 的元素替换为 $c_i$。

她想知道，每一次指挥过后，数组 $a$ 的元素之和 $S$。

输入格式

输入数据第一行为 $n$。

第二行为 $n$ 个正整数 $[a_1, a_2, \cdots, a_n]$。

第三行一个正整数 $q$，表示操作次数，接下来 $q$ 行每行两个正整数 $b_i$ 和 $c_i$，代表一次具体操作。

输出格式

输出 $q$ 行，每行一个整数 $S_i$，表示每次操作之后数组 $a$ 的元素之和。

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

10
11
14

数据范围

对于 $60 \%$ 的数据，$n,q \leq 10^3$； 对于 $100 \%$ 的数据，$1 \leq n,q,a_i,b_i,c_i \leq 10^5$。