Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official.
×

No tag edit access

B. Restaurant

time limit per test

4 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputA 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^{5}) — number of orders. The following *n* lines contain integer values *l*_{i} and *r*_{i} each (1 ≤ *l*_{i} ≤ *r*_{i} ≤ 10^{9}).

Output

Print the maximal number of orders that can be accepted.

Examples

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

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/16/2018 01:01:14 (f1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|