← 返回题目列表

AtCoder · abc313_h

Ex. 合影

中文机器翻译题面 查看原题

分数: 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