分数: 1500 点
问题陈述
你有 N 套 S_1, S_2, \ldots, S_N。 最初,对于每个 i 来自 1 to N,设置 S_i 仅包含整数 i (即 S_i = \{i\}).
您可以执行以下操作:
- 选择任意 i 与 1 \le i \le N-1。 让 U = S_i \cup S_{i+1} — 集合的并集 S_i 和 S_{i+1}。 然后,将两者替换 S_i 和 S_{i+1} 与 U.
您想要执行上述有限数量的操作(可能为零),以获得配置,其中 S_i = \{L_i, L_i+1, \ldots, R_i-1, R_i\} 对于所有人 i 来自 1 to N。能达到这个配置吗?如果可能的话,还要找到达到该目标所需的最少操作数。
约束
- 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\}