该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Background

Python users can try submitting with pypy3.

NOIP is coming soon, and yyy is very nervous!

Problem Description

There are $n$ contests on various OJ sites, and the start and end times of each contest are known.

yyy believes that the more contests he attends, the better he will do in NOIP (not really). So, he wants to know the maximum number of contests he can attend.

Since yyy is a "juruo" (rookie), if he decides to attend a contest, he must see it through from start to finish, and he cannot attend $2$ or more contests at the same time.

Input Format

The first line contains an integer $n$. The next $n$ lines each contain $2$ integers $a_{i},b_{i}\ (a_{i}<b_{i})$, representing the start and end times of a contest.

Output Format

Output a single integer: the maximum number of contests he can attend.

3
0 2
2 4
1 3

2

Hint

• For $20\%$ of the testdata, $n \le 10$.
• For $50\%$ of the testdata, $n \le 10^3$.
• For $70\%$ of the testdata, $n \le 10^{5}$.
• For $100\%$ of the testdata, $1\le n \le 10^{6}$, $0 \le a_{i} < b_{i} \le 10^6$.

Translated by ChatGPT 5