题目描述

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

你可以执行以下操作：

• 选择任意的 $i$，其中 $1 \leq i \leq N-1$。令 $U = S_i \cup S_{i+1}$，即集合 $S_i$ 和 $S_{i+1}$ 的并集。然后，将 $S_i$ 和 $S_{i+1}$ 替换为 $U$。

你希望通过有限次的上述操作（可能为零次），得到一种配置，其中对于所有的 $i$，有 $S_i = \{L_i, L_{i+1}, \ldots, R_{i-1}, R_i\}$。是否可能达到这种配置？如果可能，还要找到达到该配置所需的最小操作次数。

约束条件

• $1 \leq N \leq 5 \times 10^5$
• $1 \leq L_i \leq R_i \leq 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\}$