RT

题目描述

给出 $n$ 个集合 $S_1,S_2,...,S_n$，起初这些集合满足 $S_i=\{i\}$。你被允许执行如下操作任意次：

选择任意一个满足 $1 \leqslant i < n$ 的整数 $i$，首先计算 $U=S_i \cup S_{i+1}$，然后将 $S_i$ 和 $S_{i+1}$ 均置为 $U$（即选择两个相邻的集合，把它们均变为这两个集合的并集）。

请输出至少需要多少次操作（可能是 $0$ 次）才能使得对于所有 $i$ 均有 $S_i=\{L_i,L_i+1,...,R_i-1,R_i\}$。如果无论如何操作都无法实现，输出 $-1$。

输入格式

第一行一个整数 $n$，代表集合数量。

接下来 $n$ 行，每行一对整数 $L_i,R_i$，表示第 $i$ 个集合最终应为 $\{L_i,L_i+1,...,R_i-1,R_i\}$。

输出格式

如果能够满足要求，输出一行一个整数 $Ans$，表示所需的最少步数。否则，输出 $-1$。

数据范围

对于 $100\%$ 的数据，满足 $1 \leqslant n \leqslant 5 \times 10^5$，$1 \leqslant L_i \leqslant R_i \leqslant n$。

Markdown:

### 题目描述

给出 $n$ 个集合 $S_1,S_2,...,S_n$，起初这些集合满足 $S_i=\{i\}$。你被允许执行如下操作任意次：

选择任意一个满足 $1 \leqslant i < n$ 的整数 $i$，首先计算 $U=S_i \cup S_{i+1}$，然后将 $S_i$ 和 $S_{i+1}$ 均置为 $U$（即选择两个相邻的集合，把它们均变为这两个集合的并集）。

请输出至少需要多少次操作（可能是 $0$ 次）才能使得对于所有 $i$ 均有 $S_i=\{L_i,L_i+1,...,R_i-1,R_i\}$。如果无论如何操作都无法实现，输出 $-1$。

### 输入格式

第一行一个整数 $n$，代表集合数量。

接下来 $n$ 行，每行一对整数 $L_i,R_i$，表示第 $i$ 个集合最终应为 $\{L_i,L_i+1,...,R_i-1,R_i\}$。

### 输出格式

如果能够满足要求，输出一行一个整数 $Ans$，表示所需的最少步数。否则，输出 $-1$。

### 数据范围

对于 $100\%$ 的数据，满足 $1 \leqslant n \leqslant 5 \times 10^5$，$1 \leqslant L_i \leqslant R_i \leqslant n$。