7011: ABC171 —— D - Replacing
[Creator : ]
Description
You have a sequence $A$ composed of $N$ positive integers: $A_{1}, A_{2}, \cdots, A_{N}$.
You will now successively do the following $Q$ operations:
You will now successively do the following $Q$ operations:
- In the $i$-th operation, you replace every element whose value is $B_{i}$ with $C_{i}$.
Input
Input is given from Standard Input in the following format:
$N$
$A_{1}\ A_{2}\ \cdots\ A_{N}$
$Q$
$B_{1}\ C_{1}$
$B_{2}\ C_{2}$
$\vdots$
$B_{Q}\ C_{Q}$
$N$
$A_{1}\ A_{2}\ \cdots\ A_{N}$
$Q$
$B_{1}\ C_{1}$
$B_{2}\ C_{2}$
$\vdots$
$B_{Q}\ C_{Q}$
Output
Print $Q$ integers $S_{i}$ to Standard Output in the following format:
$S_{1}$
$S_{2}$
$\vdots$
$S_{Q}$
Note that $S_{i}$ may not fit into a $32$-bit integer.
Constraints
All values in input are integers.
$1 \leq N, Q, A_{i}, B_{i}, C_{i} \leq 10^{5}$
$B_{i} \neq C_{i}$
$1 \leq N, Q, A_{i}, B_{i}, C_{i} \leq 10^{5}$
$B_{i} \neq C_{i}$
Sample 1 Input
4
1 2 3 4
3
1 2
3 4
2 4
Sample 1 Output
11
12
16
Initially, the sequence $A$ is $1,2,3,4$.
After each operation, it becomes the following:
- $2, 2, 3, 4$
- $2, 2, 4, 4$
- $4, 4, 4, 4$
Sample 2 Input
4
1 1 1 1
3
1 2
2 1
3 5
Sample 2 Output
8
4
4
Sample 3 Input
2
1 2
3
1 100
2 100
100 1000
Sample 3 Output
102
200
2000