建筑需要整体结构来维持，不能只靠地基…… —— LazyJazz

[万圣节Party进行时……]

LazyJazz号召大家一起来搭积木，搭一座巨高巨高的积木塔。大家一起先构思了一个最终目标，即最终塔的形状，然后打算分工搭出若干小积木塔，每个小积木塔对应最终塔的某一段结构，最后一个一个摞起来。

积木塔的最终形态由 $n$ 块密度均匀且相等，宽、高相等，长度不定的积木上下摞在一起，宽对齐，从上至下数第 $i$ 块积木覆盖了横坐标对应 $L_i$ 至 $R_i$ 的范围（包含 $L_i$ , $R_i$ 两点），长度为 $R_i - L_i$ 单位长度。根据前面的描述，可以得出结论，每块积木的质量正比于其长度。

由于是积木塔，所以塔有可能不稳定，稳定的判定条件是：若一个积木塔有 $m$ 层，当且仅当对于任意 $i∈[1,m)$ ，从上至下数，前 $i$ 块积木的重心落在第 $i+1$ 块积木的覆盖范围内，则稳定，否则不稳定。前 $i$ 块积木的重心为前 $i$ 块积木的几何中心，以质量为权重的带权平均位置。

例如:

一个 $3$ 层的积木塔，从上到下，第一层覆盖范围为 $[1,3]$,第二层覆盖范围为 $[0,2]$,第三层覆盖范围为 $[1,2]$，其结构是稳定的。

.##
##.
.#.

一个 $3$ 层的积木塔，从上到下，第一层覆盖范围为 $[1,3]$,第二层覆盖范围为 $[0,2]$,第三层覆盖范围为 $[0,1]$，其结构是不稳定的（即便每两层分开看都稳定）。

.##
##.
#..

一个 $3$ 层的积木塔，从上到下，第一层覆盖范围为 $[0,8]$,第二层覆盖范围为 $[4,12]$,第三层覆盖范围为 $[5,7]$，其结构是稳定的（即便最底下两层看上去不稳定）。

########....
....########
.....##.....

LazyJazz想要把塔搭好，又要避免中间过程出现不稳定结构（即最终积木塔分解成的一段一段的小积木塔都稳定，且在一个一个摞小积木塔时的所有中间形态也都稳定），所以需要聪明的你帮忙提前规划好该如何把最终结构拆成小积木塔结构，保证拆解后层数最多的小积木塔层数最小。你只需要回答拆解后层数最多的小积木塔层数最小是多少即可。

输入格式

第一行一个正整数 $n$ ，表示最终积木塔一共有 $n$ 层

接下来 $n$ 行，每行两个非负整数 $L_i, R_i$ ，表示从上往下数第 $i$ 层的积木覆盖范围为 $[L_i,R_i]$

保证输入时给出的积木塔结构是稳定的

输出格式

一个正整数，表示所有可行拆解方案中，拆解后层数最多的小积木塔层数最小是多少？

3
1 3
0 2
1 2

1

该组样例对应题目描述中的第一个例子。可以看出来，即便一个积木一个积木地往上摞，也不会出现不稳定结构。

3
0 8
4 12
5 7

2

该组样例对应题目描述中的第三个例子。最优方案是：从上往下数，前两层划分为一小积木塔，最后一层单独划分成一个小积木塔。

5
3 13
3 13
0 8
4 12
7 8

3

结构如图所示

...##########
...##########
########.....
....########.
.......#.....

最优方案是：从上往下数，前三层划分为一个小积木塔，后两层分开或者不分开皆可。

样例四

见样例数据下载

样例五

见样例数据下载

限制与约定

由于一些原因，本题使用捆绑测试。每个子任务有若干个测试点，分为 $4$ 个子任务，你只有通过一个子任务的所有测试点才能得到这个子任务的分数。

子任务	分值	限制
1	30	$n \leq 20$
2	30	$n \leq 100$
3	35	$n \leq 1000$
4	5	$n \leq 100000$

$0 \leq L_i < R_i \leq 10^4$

保证输入时给出的积木塔结构是稳定的

时间限制：$1\texttt{s}$

空间限制：$256\texttt{MB}$

下载

样例数据下载