Problem Background

Xiao C loves data structures involving interval operations because such problems always have an easy $\mathcal{O}\left(n^2\right)$ partial score.

Problem Description

This problem has a large input size, it is recommended to use fast input methods, refer to Contest Announcement Board

Xiao C has a sequence $a$ of length $n$, where the $i$-th element is $a_i$.

$a$ is a permutation of $1$ to $n$ (i.e., each number from $1$ to $n$ appears exactly once in $a$).

Define $\operatorname{Mex}_{l,r}$ as the smallest positive integer not present in $\{a_l, a_{l+1}, \cdots, a_{r-1}, a_r\}$.

For example, $\operatorname{Mex}\{2,3\}=1, \operatorname{Mex}\{1,2,3\}=4$.

Xiao C also has a sequence $f$ of length $n$.

An interval $\left[l,r\right]$ is considered valid if and only if
$$f_{r-l+1} < \operatorname{Mex}_{l,r}$$

Xiao C wants you to tell him the length of the shortest valid interval. Specifically, if no valid interval exists, output 0.

Input Format

The first line contains a positive integer $n$.

The second line contains $n$ positive integers $a_1, a_2, \cdots, a_n$.

The third line contains $n$ positive integers $f_1, f_2, \cdots, f_n$.

Output Format

A single integer representing the length of the shortest valid interval.

Sample Input and Output

Sample Input #1

5
2 3 1 5 4
2 2 3 4 5

Sample Output #1

3

Sample Input #2

5
2 3 1 5 4
1 2 2 4 5

Sample Output #2

1

Sample Input #3

5
1 3 4 2 5
6 7 8 9 10

Sample Output #3

0

Sample Input #4

See attachment

Sample Output #4

See attachment

Notes/Hints

Sample Explanation

For #1, it is easy to find that $\left[1,3\right]$ is the shortest valid interval.

For #2, it is easy to find that $\left[3,3\right]$ is the shortest valid interval.

For #3, it is easy to find that there is no valid interval.

For $10\%$ of the data, $1 \leq n \leq 100$.

For $20\%$ of the data, $1 \leq n \leq 1000$.

For another $10\%$ of the data, $f$ is non-increasing, i.e., $f_1 \geq f_2 \geq \cdots \geq f_n$, and $1 \leq n \leq 10^6$.

For $100\%$ of the data, $1 \leq n \leq 4 \times 10^6, 1 \leq f_i \leq 10^9$.

见题面 Input 部分

见题面 Output 部分