Restaurant

题意翻译

一家餐馆收到了N张出租的订单。每个租赁订单连续预订餐厅一段时间，第i个订单上有开始时间l[i]和结束时间r[i]（l[i]<=r[i]） 餐厅管理层可以接受和拒绝订单。问餐厅可以接受的最大订单数是多少？ 注意，餐厅不能同时做两张订单。

题目描述

A restaurant received $ n $ orders for the rental. Each rental order reserve the restaurant for a continuous period of time, the $ i $ -th order is characterized by two time values — the start time $ l_{i} $ and the finish time $ r_{i} $ ( $ l_{i}<=r_{i} $ ). Restaurant management can accept and reject orders. What is the maximal number of orders the restaurant can accept? No two accepted orders can intersect, i.e. they can't share even a moment of time. If one order ends in the moment other starts, they can't be accepted both.

输入输出格式

输入格式

The first line contains integer number $ n $ ( $ 1<=n<=5·10^{5} $ ) — number of orders. The following $ n $ lines contain integer values $ l_{i} $ and $ r_{i} $ each ( $ 1<=l_{i}<=r_{i}<=10^{9} $ ).

输出格式

Print the maximal number of orders that can be accepted.

输入输出样例

输入样例 #1

2
7 11
4 7

输出样例 #1

1

输入样例 #2

5
1 2
2 3
3 4
4 5
5 6

输出样例 #2

3

输入样例 #3

6
4 8
1 5
4 7
2 5
1 3
6 8

输出样例 #3

2