约翰尼有一个新玩具。正如您可能猜到的那样,这有点不同寻常。该玩具是从 $$$1$$$ 到 $$$n$$$ 的数字 $$$P$$$ 的排列,彼此相邻地写在一行中。
对于 $$$P_i$$$ 和 $$$P_{i + 1}$$$ 之间从 $$$1$$$ 到 $$$n - 1$$$ 的每个 $$$i$$$,都写入一个权重 $$$W_i$$$,这些权重形成从 $$$1$$$ 到 $$$n - 1$$$ 的数字排列。还有额外的权重 $$$W_0 = W_n = 0$$$。
对于 $$$\{L, L + 1, \ldots, R - 1\}$$$ 中的任何 $$$i$$$,如果 $$$W_{L - 1} < W_i$$$ 且 $$$W_R < W_i$$$,则该指令将子段 $$$[L, R]$$$ 定义为良好。对于这样的子段,它还将 $$$W_M$$$ 定义为集合 $$$\{W_L, W_{L + 1}, \ldots, W_{R - 1}\}$$$ 的最小值。
现在乐趣开始了。一步操作中,玩家可以选择其中一个好的子片段,将其切成 $$$[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$$$。
Johnny的妹妹Megan认为规则太复杂,所以她想通过选择一对索引$$$X$$$和$$$Y$$$来测试她的弟弟,并交换$$$P_X$$$和$$$P_Y$$$($$$X$$$可能等于$$$Y$$$)。在每个姐妹交换之后,约翰尼想知道,从当前的 $$$P$$$ 开始并进行合法的移动,他能实现的最少反转次数是多少?
您可以假设输入是随机生成的。 $$$P$$$ 和 $$$W$$$ 是在所有排列中独立且等概率地选择的;此外,梅根的请求是在所有指数对上独立且等概率地选择的。
输入
第一行包含单个整数 $$$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$$$ 元素的索引。查询不是独立的;在每个之后,排列都会改变。
输出
输出 $$$q$$$ 行。第 $$$i$$$ 行应恰好包含一个整数 - 排列中反转的最小数量,可以通过在第一个 $$$i$$$ 查询之后从 $$$P$$$ 开始并进行游戏指令中描述的移动来获得。
示例
输入 #1
3 3 2 1 2 1 3 1 3 3 2 3 1
输出 #1
0 1 0
输入 #2
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
输出 #2
3 1 2 1 2 3 3
注意
考虑第一个样本。在第一个查询之后,$$$P$$$ 已排序,因此我们已经实现了没有反转的排列。
第二次查询后,$$$P$$$等于[$$$1$$$,$$$3$$$,$$$2$$$],有一次反转,可以证明$$$0$$$反转是不可能实现的。
最终$$$P$$$等于[$$$2$$$,$$$3$$$,$$$1$$$];我们可以对整个排列进行移动,因为它本身就是一个很好的子段,这会导致 $$$P$$$ 等于 [$$$1$$$, $$$2$$$, $$$3$$$],其中有 $$$0$$$ 反转。