P8087 "JROI-5" Interval

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.

**This problem has a large input size. It is recommended to use a fast input method. You may refer to the [contest bulletin board](https://www.luogu.com.cn/paste/lueudpd5).** 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 $$f_{r-l+1}< \operatorname{Mex}_{l,r}$$ Little C wants you to tell him the length of the shortest valid interval. In particular, if no interval is valid, output `0`.

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 one integer in a single line, indicating the length of the shortest valid interval.

[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