配点 : 100 点
問題文
(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 。
制約
- 1 \leq N \leq 200000
- P,Q 是 您也可以写 (1,2,\dots,N) 的排列 给出了
- 所有输入均为整数
部分点
- N \leq 3000 的数据集,30 授予积分。
- 如果对于没有附加约束的数据集,除了上述之外,答案是正确的, 70 授予积分。
入力
输入是按以下格式从标准输入给出的。
N P_1 P_2 \dots P_N Q_1 Q_2 \dots Q_N
出力
打印答案。 来自
入力例 1
3 2 3 1 1 3 2
出力例 1
6
S=000,001,010,101,011,111(4:16 修改) 6 可以有街道。
入力例 2
5 3 4 2 1 5 3 1 2 5 4
出力例 2
11
入力例 3
10 9 2 10 3 4 8 6 7 5 1 7 8 3 4 1 6 5 2 10 9
出力例 3
43