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} < 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.

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

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.