Restaurant

Time Limit:4000MS     Memory Limit:262144KB     64bit IO Format:%I64d & %I64u

Submit 

Description

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.

Input

The first line contains integer number n (1 ≤ n ≤ 5·10⁵) — number of orders. The following n lines contain integer values l_i and r_ieach (1 ≤ l_i ≤ r_i ≤ 10⁹).

Output

Print the maximal number of orders that can be accepted.

Sample Input

Input

2 7 11 4 7

Output

1

Input

5 1 2 2 3 3 4 4 5 5 6

Output

3

Input

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

Output

2

/*题意：给你餐厅n组客人就餐时间（起始时间，终止时间）如果时间有重叠的话，那么两组客人不能同时用餐，问餐厅最多接纳多少组客人初步思路：按照终止时间排序，然后贪心*/#include 
         
          using namespace std;struct node{    int Frist,End;    bool operator <(const node &other) const{        return End
          
           last){                res++;                last=fr[i].End;            }        }        printf("%d\n",res);    }    return 0;}