题目描述

有 $N$ 个集合 $S_1, S_2, \ldots, S_N$。初始时，对于每个 $1 \leq i \leq N$，集合 $S_i$ 只包含整数 $i$（即 $S_i = \{i\}$）。

你可以进行如下操作：

• 任意选择一个满足 $1 \leq i \leq N-1$ 的 $i$，令 $U = S_i \cup S_{i+1}$（即 $S_i$ 和 $S_{i+1}$ 的并集）。然后，将 $S_i$ 和 $S_{i+1}$ 都替换为 $U$。

你的目标是通过有限次操作（可以为 $0$ 次），使得对于所有 $1 \leq i \leq N$，都有 $S_i = \{L_i, L_i+1, \ldots, R_i-1, R_i\}$。请判断是否可以达到目标状态。如果可以，请求出所需的最小操作次数。

输入格式

输入以如下格式从标准输入读入。

$N$ $L_1$ $R_1$ $L_2$ $R_2$
$\vdots$
$L_N$ $R_N$

输出格式

如果可以达到目标状态，输出所需的最小操作次数。否则，输出 $-1$。

样例 1

输入

3
1 2
1 2
1 3

输出

-1

样例 2

输入

4
1 3
1 4
1 4
2 4

输出

4

说明/提示

限制条件

• $1 \leq N \leq 5 \times 10^5$
• $1 \leq L_i \leq R_i \leq N$

样例解释 1

可以证明无法达到目标状态。

样例解释 2

可以按如下方式进行操作达到目标状态：

• 选择 $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\}$。

由 ChatGPT 4.1 翻译