Score : $650$ points

问题陈述

设有 $(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}$。若满足以下所有条件，则称这种排列方式为好的排列：

• 对于所有 $i\ (2 \leq i \leq N)$，满足 $a_i < b_i$ 或 $a_{i-1} < b_i$。
• 满足 $a_1 < b_1$。
• 满足 $a_N < b_{N+1}$。

在前排 $N!$ 种排列方式中，有多少种（模 $998244353$）可以通过重新排列后排人员使得排列变为好的排列方式？

以上为通义千问 qwen-max 翻译，仅供参考。

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 back 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

update @ 2024/3/10 08:57:03