Background

Little C likes data structures with interval operations, because such problems always have an easy-to-write $\mathcal{O}\left(n^2\right)$ partial score.

Problem Description

This problem has a large input size. It is recommended to use a fast input method. You may refer to the contest bulletin board.

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

$a$ is a permutation of $1 \sim n$ (that is, each of $1 \sim n$ appears exactly once in $a$).

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

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

Little C also has an array $f$ of length $n$.

An interval $\left[l,r\right]$ is defined to be valid if and only if

Little C wants you to tell him the length of the shortest valid interval. In particular, if no interval is valid, 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

Output one integer in a single line, indicating the length of the shortest valid interval.

5
2 3 1 5 4
2 2 3 4 5

3

5
2 3 1 5 4
1 2 2 4 5

1

5
1 3 4 2 5
6 7 8 9 10

0

见附件

见附件

Hint

[Sample Explanation]

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

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

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

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

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

For another $10\%$ of the testdata, $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 testdata, $1\leq n\leq 4\times 10^6$ and $1\leq f_i\leq 10^9$.

Translated by ChatGPT 5