P17083 [COTS 2026] Permutations / Permutacije (No testdata available)

2s, 512M

You are given two permutations $a_1\sim a_N$ and $b_1\sim b_N$ of $1\sim N$. Choose one (continuous) subarray from each permutation, $[a_{l},a_{l+1},\ldots,a_r]$ and $[b_{L},b_{L+1},\ldots,b_R]$, such that $[a_{l},a_{l+1},\ldots,a_r,b_{L},b_{L+1},\ldots,b_R]$ is a permutation of $1\sim N$. Find the number of ways to achieve this.

The first line contains a positive integer $N$ ($2\le N\le 10^6$). The second line contains $N$ integers, describing the permutation $a_1,\ldots,a_N$ of $1\sim N$. The third line contains $N$ integers, describing the permutation $b_1,\ldots,b_N$ of $1\sim N$.

Output one integer in one line, representing the answer.

### Sample Explanation - Explanation for Sample $1$ The following choices are valid: - Choose $1$ from the first permutation and choose $2, 3$ from the second permutation; - Choose $1, 2$ from the first permutation and choose $3$ from the second permutation; - And two other symmetric choices. - Explanation for Sample $3$ Choosing $[1, 3, 5]$ from the first permutation and choosing $[2, 4]$ from the second permutation is valid. ### Subtasks | Subtask | Score | Constraints | | :---: | :---: | :--- | | $1$ | $7$ | $N \leq 200$ | | $2$ | $20$ | $N \leq 2\,000$ | | $3$ | $36$ | $a_1 = b_1$ | | $4$ | $37$ | No additional constraints. | Translated by ChatGPT 5