分数: 650 点
问题陈述
(2N+1) 人们排成两排拍集体照。 有 N 前排的人;的 i- 其中第一个的高度为 A_i。 有 (N+1) 后排的人;的 i- 其中第一个的高度为 B_i。 保证了 (2N+1) 人是有区别的。 在每一行中,我们可以自由地重新排列人员。
假设前排人的身高是 a_1,a_2,\dots,a_N ,后排分别是 b_1,b_2,\dots,b_{N+1} 从左边开始。 据说这样的安排 好 如果满足以下所有条件:
- a_i < b_i or a_{i-1} < b_i 对于所有人 i\ (2 \leq i \leq N).
- a_1 < b_1.
- a_N < b_{N+1}.
其中 N! 重新排列前排的方法,有多少个,模 998244353,有没有什么办法可以重新安排后排,让排列好呢?
约束
- 1\leq N \leq 5000
- 1 \leq A_i,B_i \leq 10^9
- A_i \neq A_j\ (1 \leq i < j \leq N)
- B_i \neq B_j\ (1 \leq i < j \leq N+1)
- A_i \neq B_j\ (1 \leq i \leq N, 1 \leq j \leq N+1)
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N
A_1 A_2 \dots A_N
B_1 B_2 \dots B_{N+1}
输出
将答案打印为整数。
示例输入 1
3 1 12 6 4 3 10 9
示例输出 1
2
- 当 a = (1,12,6),我们可以让,例如, b = (4,3,10,9) 安排好。
- 当 a = (6,12,1),我们可以让,例如, b = (10,9,4,3) 安排好。
- 当 a 是其他四种方式之一,后排不重新排列(即没有任何可能的 24 候选人 b)使安排良好。
因此,答案是 2.
示例输入 2
1 5 1 10
示例输出 2
0
示例输入 3
10 189330739 910286918 802329211 923078537 492686568 404539679 822804784 303238506 650287940 1 125660016 430302156 982631932 773361868 161735902 731963982 317063340 880895728 1000000000 707723857 450968417
示例输出 3
3542400