Problem G
Yet Another Query On Array Problem

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.

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

1 2
1 3
1 2
3 5