CF689D.Friends and Subsequences

Mike and !Mike are old childhood rivals, they are opposite in everything they do, except programming. Today they have a problem they cannot solve on their own, but together (with you) — who knows?

Every one of them has an integer sequences a and b of length n. Being given a query of the form of pair of integers (l, r), Mike can instantly tell the value of while !Mike can instantly tell the value of .

Now suppose a robot (you!) asks them all possible different queries of pairs of integers (l, r) (1 ≤ l ≤ r ≤ n) (so he will make exactly n(n + 1) / 2 queries) and counts how many times their answers coincide, thus for how many pairs is satisfied.

How many occasions will the robot count?

迈克和“非迈克”是从小一起长大的宿敌，他们在所有事情上都截然相反，唯独在编程方面例外。今天，他们遇到了一个自己无法独立解决的问题，但加上你（一起合作）——谁知道呢？

他们各自拥有一个长度为 $n$ 的整数序列 $a$ 和 $b$。对于形如整数对 $(l, r)$ 的查询，迈克能立刻给出值
，
而“非迈克”能立刻给出值
。

现在假设有一个机器人（也就是你！）向他们提出所有可能的不同查询对 $(l, r)$（其中 $1 \leq l \leq r \leq n$）（因此总共会提出恰好 $\frac{n(n+1)}{2}$ 个查询），并统计他们的答案一致的次数，即满足

的对 $(l, r)$ 的个数。

机器人将统计出多少次这样的场合？

The first line contains only integer n (1 ≤ n ≤ 200 000).

The second line contains n integer numbers _a_1, _a_2, ..., a__n ( - 109 ≤ a__i ≤ 109) — the sequence a.

The third line contains n integer numbers _b_1, _b_2, ..., b__n ( - 109 ≤ b__i ≤ 109) — the sequence b.

第一行仅包含一个整数 $n$（$1 \leq n \leq 200\,000$）。

第二行包含 $n$ 个整数 $a_1,\,a_2,\,\dots,\,a_n$（$-10^9 \leq a_i \leq 10^9$）——序列 $a$。

第三行包含 $n$ 个整数 $b_1,\,b_2,\,\dots,\,b_n$（$-10^9 \leq b_i \leq 10^9$）——序列 $b$。

Print the only integer number — the number of occasions the robot will count, thus for how many pairs is satisfied.

输出唯一的整数——机器人将计数的次数，即满足条件的数对 的个数。

The occasions in the first sample case are:

1.l = 4,r = 4 since max{2} = min{2}.

2.l = 4,r = 5 since max{2, 1} = min{2, 3}.

There are no occasions in the second sample case since Mike will answer 3 to any query pair, but !Mike will always answer 1.

第一个样例中的满足条件的情况有：

1. $l = 4$，$r = 4$，因为 $\max\{2\} = \min\{2\}$。

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

第二个样例中不存在满足条件的情况，因为 Mike 对任意查询对都会回答 $3$，但 !Mike 总是回答 $1$。