分数: 600 点
问题陈述
我们有一个序列 X,最初是空的。
Takahashi 已执行以下操作 i=1,2,\ldots,N 按此顺序。
- 追加 l_i,l_i+1,\ldots,r_i 按此顺序结束 X.
找到最终的严格递增子序列的最大长度 X.
约束
- 1 \leq N \leq 2 \times 10^5
- 1 \leq l_i \leq r_i \leq 10^9
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N
l_1 r_1
\vdots
l_{N} r_{N}
输出
打印答案。
示例输入 1
4 1 1 2 4 10 11 7 10
示例输出 1
8
决赛 X is (1,2,3,4,10,11,7,8,9,10).
的 1-st, 2-nd, 3-rd, 4-th, 7-th, 8-th, 9-th,以及 10个元素形成具有最大长度的严格递增子序列。
示例输入 2
4 1 1 1 1 1 1 1 1
示例输出 2
1
决赛 X is (1,1,1,1).
示例输入 3
1 1 1000000000
示例输出 3
1000000000