Swap and Inversion Number

The inversion number of a sequence of length $N$ $\{a_1, a_2,.... . a_N\}$ is the total number of pairs ($a_i, a_j$) of elements satisfying $1 \leq i < j \leq N$ and $a_i > a_j$.

The inversion number of a sequence is also known as the number of exchanges in the elementary alignment algorithm, bubble sort.

In this problem, we perform the operation of exchanging the values of two elements in a number sequence and output the inversion number of the sequence after the exchange.

Wreate a program that reads a number sequence and information about multiple operations and outputs the result of each operation. Each operation after the first one shall be performed on the number sequence obtained as a result of the immediately preceding operation.

Input

The input is given in the following form.

$N$
$a_1$ $a_2$ ... $a_N$
$M$
$b_1$ $e_1$
$b_2$ $e_2$
:
$b_M$ $e_M$

The first line gives the number of elements of the sequence $N$ ($2 \leq N \leq 500,000$); the second line gives the value of the $i$-th element of the sequence $a_i$ ($0 \leq a_i \leq 1,000,000,000$). The values of all elements are different (if $i \ne j$, then $a_i \ne a_j$). In the subsequent line, the number of operations $M$ ($1 \leq M \leq 30,000$) is given. In the following $M$ lines, the pair of integers $b_i$ and $e_i$ ($1 \leq b_i < e_i \leq N$) representing the information of the $i$-th operation are given. $b_i$ and $e_i$ indicate that it is the values of the $b_i$-th and $e_i$-th elements of the sequence of numbers that are exchanged in the $i$-th operation.

Output

The output consists of $M$ rows. For each operation, output the result of the operation in a line.

Sample Input and Output

Sample Input

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

Sample Output

9
8
3

---