/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 800 点
問題文
ある店を訪れる N 人の客がおり、彼らを 1,\ldots,N と呼びます。客 i は時刻 A_i に店に入り、時刻 B_i に店を出ます。この店の行列は「先入れ先出し」方式であり、A_i も B_i も単調増加です。また、A_i や B_i は全て異なります。
店の入口に、客が名前を書くリストがあります。それぞれの客は、入店時か退店時に一度だけ自分の名前をリストの末尾に書きます。最終的に名前が書かれる順序は何通りありうるでしょうか。 この数を 998\,244\,353 で割った余りを求めてください。
制約
- 1 \leq N \leq 5 \cdot 10^5
- 1 \leq A_i < B_i \leq 2N
- A_i < A_{i + 1} (1 \leq i \leq N - 1)
- B_i < B_{i + 1} (1 \leq i \leq N - 1)
- A_i \neq B_j (i \neq j)
- 入力中の値は全て整数である。
入力
入力は、標準入力から以下の形式で与えられる。
N A_1 B_1 \vdots A_N B_N
出力
答えを出力せよ。
入力例 1
3 1 3 2 5 4 6
出力例 1
3
ありうる順序は (1, 2, 3), (2, 1, 3), (1, 3, 2) です。
入力例 2
4 1 2 3 4 5 6 7 8
出力例 2
1
ありうる順序は (1, 2, 3, 4) のみです。
Score : 800 points
Problem Statement
There are N customers named 1,\ldots,N visiting a shop. Customer i arrives at time A_i and leaves at time B_i. The queue order is first in-first out, so A_i are increasing, and B_i are increasing. Additionally, all A_i and B_i are pairwise distinct.
At the entrance there's a list of visitors to put their names in. Each customer will write down their name next in the list exactly once, either when they arrive or when they leave. How many different orders of names can there be in the end? Find the count modulo 998\,244\,353.
Constraints
- 1 \leq N \leq 5 \cdot 10^5
- 1 \leq A_i < B_i \leq 2N
- A_i < A_{i + 1} (1 \leq i \leq N - 1)
- B_i < B_{i + 1} (1 \leq i \leq N - 1)
- A_i \neq B_j (i \neq j)
- All values in the input are integers.
Input
Input is given from Standard Input in the following format:
N A_1 B_1 \vdots A_N B_N
Output
Print the answer.
Sample Input 1
3 1 3 2 5 4 6
Sample Output 1
3
The possible orders are (1, 2, 3), (2, 1, 3), (1, 3, 2).
Sample Input 2
4 1 2 3 4 5 6 7 8
Sample Output 2
1
The only possible order is (1, 2, 3, 4).