The restaurant received n orders for a banquet. Each order is characterized by two values: the start time of the banquet l
i and the end time r
i (l
i ≤ r
i).
The restaurant management can either accept the order or reject it. What is the maximum number of orders that can be accepted?
No two accepted orders can intersect, that is, there should not be a point in time that belongs to two accepted orders at once. If one of the orders starts at the same time as the other ends, then they cannot be accepted together.
Input:
The first line contains an integer n (1 ≤ n ≤ 200000) — the number of orders. Each of the next n lines contains a pair of integers l
i, r
i (0 ≤ l
i &le ; r
i ≤ 10
9).
Output:
Print the maximum number of orders that can be accepted.
Examples:
| Input |
Output |
2
7 11
4 7 |
1 |
5
1 2
23
34
4 5
5 6 |
3 |
6
48
15
47
25
1 3
68 |
2 |