← 返回题目列表

Codeforces · 1793/D

D. 莫斯科大猩猩

中文机器翻译题面 查看原题

冬天,莫斯科动物园的居民非常无聊,尤其是大猩猩。您决定招待它们,并将长度为 $$$n$$$ 的排列 $$$p$$$ 带到动物园。

长度 $$$n$$$ 的排列是一个由 $$$n$$$ 不同整数组成的数组,从 $$$1$$$ 到 $$$n$$$ 可以任意顺序。例如,$$$[2,3,1,5,4]$$$ 是排列,但 $$$[1,2,2]$$$ 不是排列($$$2$$$ 在数组中出现两次),并且 $$$[1,3,4]$$$ 也不是排列($$$n=3$$$,但 $$$4$$$ 出现在数组中)。

大猩猩有自己的排列 $$$q$$$,长度为 $$$n$$$。他们建议您计算整数对 $$$l, r$$$ ($$$1 \le l \le r \le n$$$) 的数量,使得 $$$\operatorname{MEX}([p_l, p_{l+1}, \ldots, p_r])=\operatorname{MEX}([q_l, q_{l+1}, \ldots, q_r])$$$。

序列的 $$$\operatorname{MEX}$$$ 是该序列中缺失的最小正整数。例如,$$$\operatorname{MEX}([1, 3]) = 2$$$、$$$\operatorname{MEX}([5]) = 1$$$、$$$\operatorname{MEX}([3, 1, 2, 6]) = 4$$$。

你不想拿自己的健康冒险,所以你不敢拒绝大猩猩。

输入

第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — 排列长度。

第二行包含 $$$n$$$ 整数 $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \le p_i \le n$$$) — 排列 $$$p$$$ 的元素。

第三行包含 $$$n$$$ 整数 $$$q_1, q_2, \ldots, q_n$$$ ($$$1 \le q_i \le n$$$) — 排列 $$$q$$$ 的元素。

输出

打印一个整数 - 合适的对 $$$l$$$ 和 $$$r$$$ 的数量。

示例

输入 #1

3
1 3 2
2 1 3

输出 #1

2

输入 #2

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

输出 #2

16

输入 #3

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

输出 #3

11

注意

在第一个示例中,两个段是正确的 – $$$[1, 3]$$$ 和 $$$\operatorname{MEX}$$$ 等于 $$$4$$$ 在两个数组中,$$$[3, 3]$$$ 和 $$$\operatorname{MEX}$$$ 等于 $$$1$$$ 在两个数组中。

例如,在第二个示例中,段 $$$[1, 4]$$$ 是正确的,段 $$$[6, 7]$$$ 不正确,因为 $$$\operatorname{MEX}(5, 4) \neq \operatorname{MEX}(1, 4)$$$。