Problem C
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\le i,j\le 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\le n\le 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\le q\le 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