P8180 "EZEC-11" Unmemorable

Unputdownable has a permutation $a$ of length $n$. While practicing monotonic stacks, he used a program to compute, for each $i$, the largest $l_i$ such that $a_{l_i} < a_i$ and $l_i < i$, and the smallest $r_i$ such that $a_{r_i} < a_i$ and $r_i > i$. In particular, if such an $l_i$ does not exist, it is defined as $0$, and if such an $r_i$ does not exist, it is defined as $n+1$. One day, Unputdownable forgot the permutation $a$, and only the arrays $l$ and $r$ **after being rearranged separately** were left. Can you help him recover the original permutation $a$? Later, since he found that $a$ cannot be recovered, you only need to tell him how many possible original permutations $a$ there are. Output the answer modulo $998244353$. The testdata guarantees that at least one solution exists.

The first line contains an integer $n$. The second line contains $n$ integers, representing the rearranged $l$. The third line contains $n$ integers, representing the rearranged $r$.

Output one line containing one integer, the number of possible permutations modulo $998244353$.

**Sample Explanation 1** One possible permutation is $\{2,5,1,3,4\}$. The $l$ array is $\{0,1,0,3,4\}$, and the $r$ array is $\{3,3,6,6,6\}$. **This problem uses bundled tests.** - Subtask 1 (5 pts): $n \leq 8$. - Subtask 2 (15 pts): $r_i \geq n$. - Subtask 3 (15 pts): $n \leq 2000$, and it is guaranteed that there exists a permutation $a$ such that the $l, r$ computed from $a$ are exactly the given ones. - Subtask 4 (25 pts): $n \leq 10^6$, and it is guaranteed that there exists a permutation $a$ such that the $l, r$ computed from $a$ are exactly the given ones. - Subtask 5 (40 pts): No special constraints. For $100\%$ of the testdata, $1 \leq n \leq 10^6$, $0 \leq l_i, r_i \leq n+1$. The testdata guarantees that at least one solution exists. Translated by ChatGPT 5