最少巡检点

题目描述

一条长廊上有 $n$ 个需要巡检的区域，第 $i$ 个区域对应闭区间 $[l_i,r_i]$。现在要在长廊上设置若干个巡检点，只要某个区域内至少包含一个巡检点，就认为该区域被覆盖。请计算至少需要设置多少个巡检点，才能覆盖所有区域。巡检点可以设置在整数位置。

输入格式

第一行输入整数 $n$。接下来 $n$ 行，每行两个整数 $l_i,r_i$。

输出格式

输出最少巡检点数量。

样例

5
1 4
2 5
7 9
8 10
9 11

2

说明

可以在位置 4 和 9 各设置一个巡检点，覆盖全部区域。按右端点从小到大处理；当当前已选点无法覆盖新区间时，把新点放在当前区间最右端。

数据范围

$1\le n\le 2\times10^5$，$0\le l_i\le r_i\le 10^9$。