/ 
実行時間制限: 3 sec / メモリ制限: 1024 MB
配点 : 1500 点
問題文
N 個の集合 S_1, S_2, \ldots, S_N があります。はじめ、1 から N までの各 i について、集合 S_i は整数 i のみを含みます（すなわち、S_i = \{i\} です）。
あなたは、次の操作を行うことができます。
- 1 \le i \le N-1 であるような i を任意に選び、U = S_i \cup S_{i+1}（S_i と S_{i+1} の和集合）とする。 そして、S_i, S_{i+1} をともに U で置き換える。
あなたの目標は、有限回の操作を行い（0 回でもよい）、1 から N までの全ての i について S_i = \{L_i, L_i+1, \ldots, R_i-1, R_i\} であるような状態に至ることです。これは可能でしょうか。可能であるなら、それに必要な最小の操作回数も求めてください。
制約
- 1 \le N \le 5\cdot 10^5
- 1 \le L_i \le R_i \le N
入力
入力は以下の形式で標準入力から与えられる。
N L_1 R_1 L_2 R_2 \vdots L_N R_N
出力
目標状態が到達可能なら、到達に必要な最小の操作回数を出力せよ。そうでなければ、-1 を出力せよ。
入力例 1
3 1 2 1 2 1 3
出力例 1
-1
目標状態が到達不能であることを証明できます。
入力例 2
4 1 3 1 4 1 4 2 4
出力例 2
4
以下のように操作を行うことで到達可能です。
- i = 2 を選び、S_1 = \{1\}, S_2 = \{2, 3\}, S_3 = \{2, 3\}, S_4 = \{4\} とする
- i = 1 を選び、S_1 = \{1, 2, 3\}, S_2 = \{1, 2, 3\}, S_3 = \{2, 3\}, S_4 = \{4\} とする
- i = 3 を選び、S_1 = \{1, 2, 3\}, S_2 = \{1, 2, 3\}, S_3 = \{2, 3, 4\}, S_4 = \{2, 3, 4\} とする
- i = 2 を選び、S_1 = \{1, 2, 3\}, S_2 = \{1, 2, 3, 4\}, S_3 = \{1, 2, 3, 4\}, S_4 = \{2, 3, 4\} とする
Score : 1500 points
Problem Statement
You have N sets S_1, S_2, \ldots, S_N. Initially, for each i from 1 to N, set S_i contains only integer i (that is, S_i = \{i\}).
You are allowed to perform the following operation:
- Choose any i with 1 \le i \le N-1. Let U = S_i \cup S_{i+1} ー the union of sets S_i and S_{i+1}. Then, replace both S_i and S_{i+1} with U.
You want to perform a finite number of operations above (maybe zero), to get a configuration, in which S_i = \{L_i, L_i+1, \ldots, R_i-1, R_i\} for all i from 1 to N. Is it possible to reach this configuration? If it is possible, also find the smallest number of operations needed to reach it.
Constraints
- 1 \le N \le 5\cdot 10^5
- 1 \le L_i \le R_i \le N
Input
Input is given from Standard Input in the following format:
N L_1 R_1 L_2 R_2 \vdots L_N R_N
Output
If it is possible to reach the required configuration, output the smallest number of operations needed to do it. Otherwise, output -1.
Sample Input 1
3 1 2 1 2 1 3
Sample Output 1
-1
It can be proved that it's impossible to obtain the required configuration.
Sample Input 2
4 1 3 1 4 1 4 2 4
Sample Output 2
4
We can perform the following sequence of operations:
- Choose i = 2, get S_1 = \{1\}, S_2 = \{2, 3\}, S_3 = \{2, 3\}, S_4 = \{4\}
- Choose i = 1, get S_1 = \{1, 2, 3\}, S_2 = \{1, 2, 3\}, S_3 = \{2, 3\}, S_4 = \{4\}
- Choose i = 3, get S_1 = \{1, 2, 3\}, S_2 = \{1, 2, 3\}, S_3 = \{2, 3, 4\}, S_4 = \{2, 3, 4\}
- Choose i = 2, get S_1 = \{1, 2, 3\}, S_2 = \{1, 2, 3, 4\}, S_3 = \{1, 2, 3, 4\}, S_4 = \{2, 3, 4\}