← 返回题目列表

AtCoder · arc159_d

D. 最长递增子序列2

中文机器翻译题面 查看原题

分数: 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