思路

因为 $a$ 是一个排列，所以我们可以记录 $i$ 出现的位置 $p_i$。

根据 $p_i$，我们可以递推出 $l_i$ 和 $r_i$ 满足 $\operatorname{Mex}_{l_i, r_i} = i + 1$ 且 $r_i - l_i + 1$ 最小。根据 $\operatorname{Mex}$ 的定义，$l_i = \min(l_i - 1, p_i)$，$r_i = \max(r_i - 1, p_i)$。

我们可以再处理出 $s_i$ 代表区间长度为 $i$ 的最大 $\operatorname{Mex}$ 值。

$\operatorname{Mex}$ 值为 $x$ 且长度 $l$ 最小，相当于 $x$ 就是满足长度为 $l$ 的最大 $\operatorname{Mex}$ 值，所以对于每一个 $i$，$s_{r_i - l_i + 1} = i + 1$。

如果 $L \le l$ 且 $r \le R$，$\operatorname{Mex}_{L, R} \ge \operatorname{Mex}_{l, r}$，所以 $s_i$ 还要和 $\max_{j = 1}^{i - 1} s_j$ 取最大值。

处理出 $s_i$ 后，枚举区间长度 $i$，判断是否满足 $s_i > f_i$ 即可。

代码

#include <algorithm>
#include <cstdio>

using namespace std;

int n, x, p[4000001], a[4000001], l, r, s[4000001], ans;
int main(){
	scanf("%d", &n);
	for (int i = 1;i <= n;i ++) scanf("%d", &x), p[x] = i;
	for (int i = 1;i <= n;i ++) scanf("%d", &a[i]);
	l = r = p[1], s[1] = 2;
	for (int i = 2;i <= n;i ++) l = min(l, p[i]), r = max(r, p[i]), s[r - l + 1] = i + 1;
	for (int i = 1;i <= n;i ++) s[i] = max(s[i - 1], s[i]);
	for (int i = 1;i <= n;i ++){
		if (s[i] > a[i]){
			printf("%d", i);
			return 0;
		}
	}
	printf("%d", 0);
}