Television

Interview

Time limit1sMemory limit1024 MB

Summary

Given N intervals on a line, choose the fewest intervals so that every point covered by any interval is covered by a chosen one, then print that count.

Level: Medium6 of 10
Topics: Greedy, Sorting, Intervals, Two pointers
Solved: No attempts yet

Problem

Next season, $N$ new TV series will begin airing. Today the first episode of each series is broadcast once: the $i$ -th series starts at time $a_i$ and ends at time $b_i$ . Every series airs on a different channel, so their broadcast times may overlap.

You plan to watch TV all day and decide which series are worth following for the rest of the season. You want to spend this time as well as possible: at every moment during which at least one series is airing, you want to be watching one of them. At the same time, following too many different series all season would be exhausting, so you want the number of series you follow to be as small as possible.

Under these conditions, what is the minimum number of series you must follow?

Input

The first line contains the number of series $N$ . Each of the next $N$ lines contains two integers $a_i$ and $b_i$ ( $a_i < b_i$ ), the start and end times of the $i$ -th series' broadcast.

Output

Print a single integer: the minimum number of series you must follow so that, at every moment during which some series is airing, you are watching one of the followed series.

Constraints

$1 \le N \le 100\,000$
$1 \le a_i < b_i \le 1\,000\,000$

Examples3

Example 1
Input
```
4
7 8
3 6
4 6
2 5
```
Expected output
```
3
```
Example 2
Input
```
1
5 10
```
Expected output
```
1
```
Example 3
Input
```
2
1 2
4 5
```
Expected output
```
2
```