题目描述

猫猫正陪 Zenith 玩着游戏呢，猫猫突然意识到他还有工作没完成，老板先前交给了他一个任务让他帮忙安排会议。公司有一间会议室，同一时间只能举办一场会议。现在有 $n$ 场会议申请，每场会议给出开始时间 $l_i$ 和结束时间 $r_i$，会议室不能重叠使用，每一场会议结束后立刻可以开始下一场，老板想知道最多可以开多少场会议。猫猫急着陪 Zenith 玩游戏，希望聪明的你可以帮帮他。

输入格式

第一行一个整数 $n$（$1 \le n \le 2 \times 10^5$），表示共有 $n$ 场会议；接下来 $n$ 行，每行两个用空格隔开的整数 $l_i, r_i$（$1 \le l_i \le r_i \le 10^9$），分别表示第 $i$ 场会议的开始时间和结束时间。

输出格式

输出最大活动场数。

5
1 3
2 4
3 5
4 6
5 7

3

提示说明

按结束时间从早到晚贪心选择即可。样例中依次可以选择 $[1,3]$、$[3,5]$、$[5,7]$（上一场结束的时刻可以立刻开始下一场），共 $3$ 场。