Problem C
Yet Another Query On Array Problem
Languages
en
is
You are given an array of $n$ integers and then $q$ queries. Each query consists of two indices $1 \leq i, j \leq n$. If the $i$-th value in the list is $x$ and the $j$-th value in the list is $y$, then all instances of $x$ in the list should be replaced by a $y$. Then the number of $x$-es that were in the list before the change should be printed, followed by a single space, and then the number of $y$-s in the list after the change should be printed.
Input
The input starts with a single integer $1 \leq n \leq 2 \cdot 10^5$. Then the $n$ integers in the array are written on a single line, separated by spaces, in order. The integers in the array are in the interval $[-10^9, 10^9]$. Then there is a single line with $1 \leq q \leq 2 \cdot 10^5$. Finally there are $q$ lines, each with two indices $i, j$ separated by a space, as described above.
Output
Two integers separated by a space on their own line for each query, as described above.
Sample Input 1 | Sample Output 1 |
---|---|
6 1 2 3 4 5 6 4 2 4 3 4 6 5 4 5 |
1 2 1 3 1 2 3 5 |