F. Johnny and New Toy
time limit per test
15 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Johnny has a new toy. As you may guess, it is a little bit extraordinary. The toy is a permutation $$$P$$$ of numbers from $$$1$$$ to $$$n$$$, written in one row next to each other.

For each $$$i$$$ from $$$1$$$ to $$$n - 1$$$ between $$$P_i$$$ and $$$P_{i + 1}$$$ there is a weight $$$W_i$$$ written, and those weights form a permutation of numbers from $$$1$$$ to $$$n - 1$$$. There are also extra weights $$$W_0 = W_n = 0$$$.

The instruction defines subsegment $$$[L, R]$$$ as good if $$$W_{L - 1} < W_i$$$ and $$$W_R < W_i$$$ for any $$$i$$$ in $$$\{L, L + 1, \ldots, R - 1\}$$$. For such subsegment it also defines $$$W_M$$$ as minimum of set $$$\{W_L, W_{L + 1}, \ldots, W_{R - 1}\}$$$.

Now the fun begins. In one move, the player can choose one of the good subsegments, cut it into $$$[L, M]$$$ and $$$[M + 1, R]$$$ and swap the two parts. More precisely, before one move the chosen subsegment of our toy looks like: $$$$$$W_{L - 1}, P_L, W_L, \ldots, W_{M - 1}, P_M, W_M, P_{M + 1}, W_{M + 1}, \ldots, W_{R - 1}, P_R, W_R$$$$$$ and afterwards it looks like this: $$$$$$W_{L - 1}, P_{M + 1}, W_{M + 1}, \ldots, W_{R - 1}, P_R, W_M, P_L, W_L, \ldots, W_{M - 1}, P_M, W_R$$$$$$ Such a move can be performed multiple times (possibly zero), and the goal is to achieve the minimum number of inversions in $$$P$$$.

Johnny's younger sister Megan thinks that the rules are too complicated, so she wants to test her brother by choosing some pair of indices $$$X$$$ and $$$Y$$$, and swapping $$$P_X$$$ and $$$P_Y$$$ ($$$X$$$ might be equal $$$Y$$$). After each sister's swap, Johnny wonders, what is the minimal number of inversions that he can achieve, starting with current $$$P$$$ and making legal moves?

You can assume that the input is generated randomly. $$$P$$$ and $$$W$$$ were chosen independently and equiprobably over all permutations; also, Megan's requests were chosen independently and equiprobably over all pairs of indices.

Input

The first line contains single integer $$$n$$$ $$$(2 \leq n \leq 2 \cdot 10^5)$$$ denoting the length of the toy.

The second line contains $$$n$$$ distinct integers $$$P_1, P_2, \ldots, P_n$$$ $$$(1 \leq P_i \leq n)$$$ denoting the initial permutation $$$P$$$. The third line contains $$$n - 1$$$ distinct integers $$$W_1, W_2, \ldots, W_{n - 1}$$$ $$$(1 \leq W_i \leq n - 1)$$$ denoting the weights.

The fourth line contains single integer $$$q$$$ $$$(1 \leq q \leq 5 \cdot 10^4)$$$ — the number of Megan's swaps. The following $$$q$$$ lines contain two integers $$$X$$$ and $$$Y$$$ $$$(1 \leq X, Y \leq n)$$$ — the indices of elements of $$$P$$$ to swap. The queries aren't independent; after each of them, the permutation is changed.

Output

Output $$$q$$$ lines. The $$$i$$$-th line should contain exactly one integer — the minimum number of inversions in permutation, which can be obtained by starting with the $$$P$$$ after first $$$i$$$ queries and making moves described in the game's instruction.

Examples
Input
3
3 2 1
2 1
3
1 3
3 2
3 1
Output
0
1
0
Input
5
4 3 2 5 1
3 2 1 4
7
5 4
5 2
1 5
2 4
2 4
4 3
3 3
Output
3
1
2
1
2
3
3
Note

Consider the first sample. After the first query, $$$P$$$ is sorted, so we already achieved a permutation with no inversions.

After the second query, $$$P$$$ is equal to [$$$1$$$, $$$3$$$, $$$2$$$], it has one inversion, it can be proven that it is impossible to achieve $$$0$$$ inversions.

In the end, $$$P$$$ is equal to [$$$2$$$, $$$3$$$, $$$1$$$]; we can make a move on the whole permutation, as it is a good subsegment itself, which results in $$$P$$$ equal to [$$$1$$$, $$$2$$$, $$$3$$$], which has $$$0$$$ inversions.