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。