AT_pakencamp_2024_day3_1_m Two Permutations

给定 $(1,2,\dots,N)$ 的两个排列 $P, Q$。 请计算，在以下步骤下可能生成的长度为 $N$ 的 $01$ 序列 $S$ 的个数，并将结果对 $998244353$ 取模。 - 准备一个满足下述条件的 $(1,2,\dots,2N)$ 的排列 $R$。 - 对于每个整数 $i$ $(1 \leq i \leq N)$，$R_1,R_2,\dots,R_N$ 中第 $P_i$ 小的元素是 $R_i$。 - 对于每个整数 $i$ $(1 \leq i \leq N)$，$R_{N+1},R_{N+2},\dots,R_{2N}$ 中第 $Q_i$ 小的元素是 $R_{N+i}$。 - 对于 $i=1,2,\dots,N$，如果 $R_i < R_{N+i}$，则 $S_i=1$；如果 $R_i > R_{N+i}$，则 $S_i=0$。

输入以以下格式从标准输入读入。 > $N$ $P_1$ $P_2$ $\dots$ $P_N$ $Q_1$ $Q_2$ $\dots$ $Q_N$

输出答案。

## 部分得分 - 对于满足 $N \leq 3000$ 的数据集，正确解答可得 $30$ 分。 - 对于没有额外限制的数据集，正确解答可再得 $70$ 分。 ## 样例解释 1 对于 $S=000,001,010,101,011,111$（已于 4:16 修正），共有 $6$ 种情况。 ## 数据范围 - $1 \leq N \leq 200000$ - $P, Q$ 是 $(1,2,\dots,N)$ 的排列 - 输入均为整数。 由 ChatGPT 5 翻译