题目描述

现在有 $n$ 个比赛，每个比赛的开始、结束时间已知。

如果要参加一个比赛，就必须完整参加，且不能同时参加两个及以上的比赛。

求最多能够参加多少个比赛。

输入格式

第一行输入一个整数 $n$。

接下来 $n$ 行，每行输入两个整数 $a_i,b_i\ (a_i<b_i)$，表示比赛的开始时间和结束时间。

输出格式

输出一个整数，表示最多能够参加的比赛数目。

3
0 2
2 4
1 3

2

数据范围

• 对于 $20\%$ 的数据，$n \le 10$；
• 对于 $50\%$ 的数据，$n \le 10^3$；
• 对于 $70\%$ 的数据，$n \le 10^{5}$；
• 对于 $100\%$ 的数据，$1\le n \le 10^{6}$，$0 \le a_i < b_i \le 10^6$。