103137: [Atcoder]ABC313 Ex - Group Photo

Problem Statement

$(2N+1)$ people are forming two rows to take a group photograph. There are $N$ people in the front row; the $i$-th of them has a height of $A_i$. There are $(N+1)$ people in the back row; the $i$-th of them has a height of $B_i$. It is guaranteed that the heights of the $(2N+1)$ people are distinct. Within each row, we can freely rearrange the people.

Suppose that the heights of the people in the front row are $a_1,a_2,\dots,a_n$ from the left, and those in the black row are $b_1,b_2,\dots,b_{n+1}$ from the left. This arrangement is said to be good if all of the following conditions are satisfied:

• $a_i < b_i$ or $a_{i-1} < b_i$ for all $i\ (2 \leq i \leq N)$.
• $a_1 < b_1$.
• $a_N < b_{N+1}$.

Among the $N!$ ways to rearrange the front row, how many of them, modulo $998244353$, are such ways that we can rearrange the back row to make the arrangement good?

Constraints

• $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)$
• All input values are integers.

Input

The input is given from Standard Input in the following format:

$N$
$A_1$ $A_2$ $\dots$ $A_N$
$B_1$ $B_2$ $\dots$ $B_{N+1}$

Output

Print the answer as an integer.

Sample Input 1

3
1 12 6
4 3 10 9

Sample Output 1

2

• When $a = (1,12,6)$, we can let, for example, $b = (4,3,10,9)$ to make the arrangement good.
• When $a = (6,12,1)$, we can let, for example, $b = (10,9,4,3)$ to make the arrangement good.
• When $a$ is one of the other four ways, no rearrangement of the back row (that is, none of the possible $24$ candidates of $b$) makes the arrangement good.

Thus, the answer is $2$.

Sample Input 2

1
5
1 10

Sample Output 2

0

Sample Input 3

10
189330739 910286918 802329211 923078537 492686568 404539679 822804784 303238506 650287940 1
125660016 430302156 982631932 773361868 161735902 731963982 317063340 880895728 1000000000 707723857 450968417

Sample Output 3

3542400

问题描述

$(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$或$a_{i-1} < b_i$对于所有的$i\ (2 \leq i \leq N)$。
• $a_1 < b_1$。
• $a_N < b_{N+1}$。

在重新排列前排的$N!$种方法中，有多少种方法可以重新排列后排，使得排列成为好的排列？

约束条件

• $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