Moscow Gorillas

题意翻译

对于给出的两个长度为 $n$ 的排列 $p$ 和 $q$ ，请你算出有多少对 $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 $。

题目描述

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.

输入输出格式

输入格式

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 $ .

输出格式

Print a single integer — the number of suitable pairs $ l $ and $ 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

说明

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) $ .

**题意翻译**

给定两个长度为 $ n $ 的排列 $ p $ 和 $ q $，计算有多少对 $ 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) $。**题意翻译** 给定两个长度为 $ n $ 的排列 $ p $ 和 $ q $，计算有多少对 $ 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) $。