P17083 [COTS 2026] 排列 / Permutacije（暂无数据）

2s, 512M

给定两个 $1\sim N$ 的排列 $a_1\sim a_N$ 和 $b_1\sim b_N$。 在两个排列中各选出一个（连续）子串 $[a_{l},a_{l+1},\ldots,a_r],[b_{L},b_{L+1},\ldots,b_R]$，使得 $[a_{l},a_{l+1},\ldots,a_r,b_{L},b_{L+1},\ldots,b_R]$ 是 $1\sim N$ 的排列。求出能够达成目标的方案数。

第一行，正整数 $N$（$2\le N\le 10^6$）。 第二行，$N$ 个整数，描述 $1\sim N$ 的排列 $a_1,\ldots,a_N$。 第三行，$N$ 个整数，描述 $1\sim N$ 的排列 $b_1,\ldots,b_N$。

输出一行一个整数，表示答案。

### 样例解释 - 样例 $1$ 解释 以下方案是合法的： - 从第一个排列中选 $1$ 且从第二个排列中选 $2, 3$； - 从第一个排列中选 $1, 2$ 且从第二个排列中选 $3$； - 以及另外两种对称的选择。 - 样例 $3$ 解释 从第一个排列中选择 $[1, 3, 5]$ 并且从第二个排列中选择 $[2, 4]$ 是合法的。 ### 子任务 | 子任务 | 分值 | 限制条件 | | :---: | :---: | :--- | | $1$ | $7 $| $N \leq 200$ | | $2$ | $20$ | $N \leq 2\,000$ | | $3$ | $36$ | $a_1 = b_1$ | | $4$ | $37$ | 无附加限制。 |