← 返回题目列表

Codeforces · 689/D

D. 朋友和后续

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

Mike 和 !Mike 是儿时的老对手,他们做什么事都相反,除了编程。今天,他们遇到了一个无法独自解决的问题,但必须(与您)一起解决——谁知道呢?

它们中的每一个都有一个长度为n的整数序列a和b。给出整数对 (l, r) 形式的查询,Mike 可以立即说出 $$\max_{i=l}^{r} a_i$$ 的值,而 !Mike 可以立即说出 $$\min_{i=l} b_i$$ 的值。

现在假设一个机器人(你!)向他们询问整数对 (l, r) (1 ≤ l ≤ r ≤ n) 的所有可能的不同查询(因此他将精确地进行 n(n + 1) / 2 次查询)并计算他们的答案重合的次数,因此 $$\max_{i=l}^{r}a_i = \min_{i=l}^{r}b_i$$ 是多少对满意。

机器人会数多少次?

输入

第一行仅包含整数 n (1 ≤ n ≤ 200 000)。

第二行包含 n 个整数 a1, a2, ..., an ( - 109 ≤ ai ≤ 109) – 序列 a。

第三行包含 n 个整数 b1, b2, ..., bn ( - 109 ≤ bi ≤ 109) – 序列 b。

输出

打印唯一的整数 - 机器人将计算的次数,因此满足多少对 $$\max_{i=l}^{r}a_i = \min_{i=l}^{r}b_i$$ 。

示例

输入 #1

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

输出 #1

2

输入 #2

3
3 3 3
1 1 1

输出 #2

0

注意

第一个示例案例中的场合是:

1.l = 4,r = 4,因为 max{2} = min{2}。

2.l = 4,r = 5,因为 max{2, 1} = min{2, 3}。

第二个示例案例中没有任何情况,因为 Mike 会对任何查询对回答 3,但 !Mike 将始终回答 1。