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