CF1361F.Johnny and New Toy

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} \lt W_i$ and $W_R \lt 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.

约翰尼有一个新玩具。如你所料，这个玩具有点特别。它是一个由 $1$ 到 $n$ 的数字构成的排列 $P$，这些数字并排写成一行。

对每个从 $1$ 到 $n - 1$ 的 $i$，在 $P_i$ 和 $P_{i + 1}$ 之间写有一个权重 $W_i$；这些权重构成 $1$ 到 $n - 1$ 的一个排列。此外还有额外的权重 $W_0 = W_n = 0$。

说明书将子段 $[L, R]$ 定义为好子段，当且仅当对任意 $i \in \{L, L + 1, \ldots, R - 1\}$，均有 $W_{L - 1} \lt W_i$ 且 $W_R \lt W_i$。对于这样的子段，还定义 $W_M$ 为集合 $\{W_L, W_{L + 1}, \ldots, W_{R - 1}\}$ 中的最小值。

现在有趣的部分开始了。在一次操作中，玩家可以选择一个好子段，并将其沿位置 $M$ 切分为 $[L, M]$ 和 $[M + 1, R]$，然后交换这两部分。更准确地说，一次操作前，所选子段的玩具外观为：

$$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$$

而操作后变为：

$$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$$

此类操作可执行多次（可能为零次），目标是使排列 $P$ 中的逆序对数量最少。

约翰尼的妹妹梅根认为规则过于复杂，于是她想通过选择某一对下标 $X$ 和 $Y$ 并交换 $P_X$ 与 $P_Y$（允许 $X = Y$）来测试哥哥。每次妹妹完成一次交换后，约翰尼都会思考：以当前的 $P$ 为起点，通过合法操作所能达到的最小逆序对数量是多少？

你可以假设输入是随机生成的：$P$ 和 $W$ 独立地、等概率地从所有排列中选取；同时，梅根的每次查询也独立地、等概率地从所有下标对中选取。

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.

第一行包含一个整数 $n$ $(2 \leq n \leq 2 \cdot 10^5)$，表示玩具的长度。

第二行包含 $n$ 个互不相同的整数 $P_1, P_2, \ldots, P_n$ $(1 \leq P_i \leq n)$，表示初始排列 $P$。第三行包含 $n - 1$ 个互不相同的整数 $W_1, W_2, \ldots, W_{n - 1}$ $(1 \leq W_i \leq n - 1)$，表示权重。

第四行包含一个整数 $q$ $(1 \leq q \leq 5 \cdot 10^4)$ —— Megan 执行的交换操作次数。接下来的 $q$ 行每行包含两个整数 $X$ 和 $Y$ $(1 \leq X, Y \leq n)$ —— 表示要交换的排列 $P$ 中元素的下标。这些查询不是相互独立的；每次交换后，排列都会被更新。

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.

输出 $q$ 行。第 $i$ 行应恰好包含一个整数——即从执行完前 $i$ 个查询后的排列 $P$ 出发，按照游戏规则进行操作后所能得到的排列的最小逆序对数量。

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.

考虑第一个样例。第一次查询后，$P$ 已经被排序，因此我们已经得到了一个没有逆序对的排列。

第二次查询后，$P$ 变为 [$1$, $3$, $2$]，它含有一个逆序对；可以证明此时无法达到 $0$ 个逆序对。

最终，$P$ 变为 [$2$, $3$, $1$]；我们可以对整个排列执行一次操作，因为该排列本身就是一个“好”的子段，操作后 $P$ 变为 [$1$, $2$, $3$]，其逆序对数量为 $0$。