← 返回题目列表

Codeforces · 809/D

D. 在波罗的海国家搭便车

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

Leha 和 Noora 决定去波罗的海国家旅行。正如您从上一个问题中知道的那样,Leha 在餐厅的停车场丢了车。不幸的是,向看守人发出的请求并没有帮助黑客找到汽车,所以朋友们决定搭便车。

他们总共打算参观n个城镇。然而事实证明,第i个镇的景点只在里到里这几天对游客开放。

该怎么办? Leha 提议为每个城镇选择 i 一天,他们将访问该城镇的时间,即区间 [li, ri] 中的任意整数 xi。之后,Noora 选择了朋友们将要访问的城镇 id1、id2、...、idk 的一些子序列,首先它们是严格递增的,即 idi < idi + 1 对于从 1 到 k - 1 的所有整数 i 而言,而且朋友访问的日期也是严格递增的,即 xidi < xidi + 1 对于从 1 到 k - 1 的所有整数 i 都成立。

请帮助Leha和Noora为每个城镇i选择这样的xi,以及城镇id1,id2,...,idk的子序列,以便朋友们可以访问最大数量的城镇。

您可能会认为 Leha 和 Noora 可以随时开始旅行。

输入

第一行包含一个整数 n (1 ≤ n ≤ 3·105),表示 Leha 和 Noora 打算访问的城镇数量。

后续 n 行中的每一行 i 包含两个整数 li, ri (1 ≤ li ≤ ri ≤ 109),表示第 i 个城镇的景点在任意一天 $$x \in [l_i, r_i]$$ 中对游客开放。

输出

打印一个整数,表示 Leha 和 Noora 可以访问的最大城镇数量。

示例

输入 #1

5
6 6
1 2
3 4
2 2
1 4

输出 #1

3

注意

考虑第一个例子。

我们采取这样的计划:第一天参观第二个城镇,第三天参观第三个城镇,第四天参观第五个城镇。这将是最佳答案。