← 返回题目列表

AtCoder · agc055_e

E. 设置合并

中文机器翻译题面 查看原题

分数: 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\}