問題文
高桥君打算挑战如下的节奏游戏。
- 有一个大按钮 N 个。要按这个按钮 1 个人正好需要 1 个人,没有其他方法可以按。
- 1 的人同一时间不能 2 个以上的按钮。
- i 个按钮,从 S_i 到 T_i 一直按到……为止 1 可以获得。这时,不必一定由同一个人从头到尾一直按着,也可以在途中更换按的人。
- 上下按钮所花费的时间,或更换按按钮的人所花费的时间,可以忽略不计。
高桥君希望通过几个人协力玩这个游戏, N-1 获得超过 分的成绩。N-1 请找出获取至少这些分数所需的最小最小值。
入力
输入是按以下格式从标准输入给出的。
N S_1 T_1 S_2 T_2 : S_N T_N
- 1 行表示按钮数量的整数 N (2 ≦ N ≦ 10^5) 。 来自行
- 2 从线 N 行给出了每个按钮的信息。其中 i (1 ≦ i ≦ N) 行中,2 整数 S_i, T_i (1 ≦ S_i < T_i ≦ 10^5) 。这是i 个按钮,从 S_i 到 T_i 一直按到……为止 1 表示可以获得分数。
出力
N-1 为了获得至少这些分数所需的最小最小值 1 行输出。在输出末尾插入换行符。
入力例1
4 1 4 1 2 2 3 3 4
出力例1
1
下图显示了每个按钮在持续按下时可以获得分数的时间。按钮 1 以外的按钮 1 全部踩到人就可以 3 得到点数。
入力例2
5 5 11 2 4 3 4 2 7 5 7
出力例2
2
入力例3
4 1 2 1 2015 2015 100000 99999 100000
出力例3
2