波罗的海搭便车

• 时间限制：2 秒
• 内存限制：256 MiB

题目描述

Leha 和 Noora 计划依次经过 $n$ 个城市。第 $i$ 个城市的景点只在第 $l_i$ 天到第 $r_i$ 天开放，两个端点都包含在内。

可以为每个城市 $i$ 任选一个整数日期 $x_i\in[l_i,r_i]$。随后，从城市序列中选择一个下标严格递增的子序列 $id_1,id_2,\ldots,id_k$，并要求相应日期也严格递增：

求最多能够选择多少个城市。旅行可以从任意日期开始。

输入格式

第一行包含一个整数 $n$，表示城市数量。

接下来 $n$ 行，每行包含两个整数 $l_i,r_i$，表示第 $i$ 个城市景点的开放日期区间。

输出格式

输出一个整数，表示最多能够选择的城市数量。

样例输入

5
6 6
1 2
3 4
2 2
1 4

样例输出

3

样例说明

可以在第 $1$ 天访问城市 $2$，第 $3$ 天访问城市 $3$，第 $4$ 天访问城市 $5$，共访问三个城市。

数据范围

对于所有数据：

• $1\le n\le 3\times 10^5$；
• $1\le l_i\le r_i\le 10^9$。