/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 650 点
問題文
2N+1 人の人が前列と後列の 2 列に並んで集合写真を取ろうとしています。 前列には 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 で割ったあまりを求めてください。
制約
- 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 がそれ以外の 4 通りであるとき、後列をどのように並べても（すなわち、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
Score : 650 points
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