Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
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-2022 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Aug/16/2022 15:46:56 (j1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|