Moscow Gorillas
Contest: Codeforces Round 852 (Div. 2)
Difficulty rating: 1800
Tags: binary search, dp, greedy, implementation, math, two pointers

In winter, the inhabitants of the Moscow Zoo are very bored, in particular, it concerns gorillas. You decided to entertain them and brought a permutation $$$p$$$ of length $$$n$$$ to the zoo.

A permutation of length $$$n$$$ is an array consisting of $$$n$$$ distinct integers from $$$1$$$ to $$$n$$$ in any order. For example, $$$[2,3,1,5,4]$$$ is a permutation, but $$$[1,2,2]$$$ is not a permutation ($$$2$$$ occurs twice in the array) and $$$[1,3,4]$$$ is also not a permutation ($$$n=3$$$, but $$$4$$$ is present in the array).

The gorillas had their own permutation $$$q$$$ of length $$$n$$$. They suggested that you count the number of pairs of integers $$$l, r$$$ ($$$1 \le l \le r \le n$$$) such that $$$\operatorname{MEX}([p_l, p_{l+1}, \ldots, p_r])=\operatorname{MEX}([q_l, q_{l+1}, \ldots, q_r])$$$.

The $$$\operatorname{MEX}$$$ of the sequence is the minimum integer positive number missing from this sequence. For example, $$$\operatorname{MEX}([1, 3]) = 2$$$, $$$\operatorname{MEX}([5]) = 1$$$, $$$\operatorname{MEX}([3, 1, 2, 6]) = 4$$$.

You do not want to risk your health, so you will not dare to refuse the gorillas.

Input format:
The first line contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the permutations length.

The second line contains $$$n$$$ integers $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \le p_i \le n$$$) — the elements of the permutation $$$p$$$.

The third line contains $$$n$$$ integers $$$q_1, q_2, \ldots, q_n$$$ ($$$1 \le q_i \le n$$$) — the elements of the permutation $$$q$$$.

Output format:
Print a single integer — the number of suitable pairs $$$l$$$ and $$$r$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first example, two segments are correct – $$$[1, 3]$$$ with $$$\operatorname{MEX}$$$ equal to $$$4$$$ in both arrays and $$$[3, 3]$$$ with $$$\operatorname{MEX}$$$ equal to $$$1$$$ in both of arrays.

In the second example, for example, the segment $$$[1, 4]$$$ is correct, and the segment $$$[6, 7]$$$ isn't correct, because $$$\operatorname{MEX}(5, 4) \neq \operatorname{MEX}(1, 4)$$$.

Example input:
3
1 3 2
2 1 3

Example output:
2

Example input:
7
7 3 6 2 1 5 4
6 7 2 5 3 1 4

Example output:
16

Editorial:
Denote by $$$pos_x$$$ the index of the number $$$x$$$ in the permutation. Subsegments with $$$\operatorname{MEX}>1$$$ are as follows $$$1 \le l \le pos_1 \le r \le n$$$.
Denote by: $$$l_x = \min{[pos_1, pos_2, \ldots, pos_x]}$$$, $$$r_x=\max{[pos_1, pos_2, \ldots, os_x]}$$$.
Subsegments with $$$\operatorname{MEX}>x$$$ are as follows $$$1 \le l \le l_x \le r_x \le r \le n$$$. Let's find all subsegments with $$$\operatorname{MEX}=x$$$.
If $$$pos_{x + 1} < l_x$$$, then the subsegments with $$$\operatorname{MEX}=x+1$$$ are as follows $$$pos_{x+1} < l \le l_x \le r_x \le r \le n$$$
If $$$l_x \le pos_{x + 1} \le r_x$$$, then there is no subsegment with $$$\operatorname{MEX}=x+1$$$
If $$$r_x <pos_{x+1}$$$, then the subsegments with $$$\operatorname{MEX}=x+1$$$ are as follows $$$1 \le l \le l_x \le r_x \le r < pos_{x+1}$$$
It remains only to intersect the sets of such subsegments for $$$p$$$ and $$$q$$$, which is done trivially.