冬天,莫斯科动物园的居民非常无聊,尤其是大猩猩。您决定招待它们,并将长度为 $$$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)$$$。