9999005 - 木板游戏

小谢在玩一个游戏,这个游戏的规则是这样的:游戏中会给你 n 个木板,第 i 个木板覆盖的区间是 [li , ri ]。 一个木板在另外一个木板上能够稳定,当且仅当上面那块木板会被完全放在下面的木板的上面,即如果把 a 放在 b 上面,要满足 lb ≤ la ≤ ra ≤ rb。他可以任选一部分木板,按照他指定的顺序依次堆成一叠,使得这一 叠木板稳定,即任意一块木板都完全在它下面一块木板上。注意只能堆成一叠,即不能在 [1, 2] 上面叠 [1, 1] 和 [2, 2]。 小谢想知道他最多能叠多少块木板。

输入

第一行一个整数 n。 后面 n 行每行两个整数 [li,ri]

输出

共一行,一个非负整数表示答案。

样例

输入

5
1 10
2 9
3 8
4 7
5 6

输出

5
时间限制 2 秒
内存限制 512 MB
统计
上一题 下一题