L - Segments Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

問題文

数直線上の N 個の区間 [L_1, R_1], [L_2, R_2], \ldots, [L_N, R_N] が与えられます。

集合 \lbrace 1, 2, \ldots, N \rbrace の部分集合 S は、次の条件を満たすとき良い集合と呼ばれます。

  • 任意の i, j \in S について、下記の 2 つのうち少なくとも一方が成り立つ。
    • 区間 [L_i, R_i] は区間 [L_j, R_j] を含む。
    • 区間 [L_j, R_j] は区間 [L_i, R_i] を含む。

ただし、区間 [L, R] が区間 [L', R'] を含むとは、L \leq L' かつ R' \leq R が成り立つことをいいます。

良い集合の要素数としてあり得る最大値を出力してください。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 0 \leq L_i < R_i \leq 10^9
  • 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

N
L_1 R_1
L_2 R_2
\vdots
L_N R_N

出力

答えを出力せよ。

入力例 1

4
1 3
2 4
3 4
1 4

出力例 1

3

集合 \lbrace 2, 3, 4 \rbrace が、要素数最大の良い集合です。実際、

  • 2, 3 \in S について、[L_2, R_2] は [L_3, R_3] を含み、
  • 2, 4 \in S について、[L_4, R_4] は [L_2, R_2] を含み、
  • 3, 4 \in S について、[L_4, R_4] は [L_3, R_3] を含みます。

よって、要素数 3 を出力します。

入力例 2

3
0 1
0 1
0 1

出力例 2

3

入力例 3

9
1 6
1 3
3 6
4 6
2 5
1 2
3 4
3 5
2 7

出力例 3

4

Problem Statement

You are given N segments [L_1, R_1], [L_2, R_2], \ldots, [L_N, R_N] on a number line.

A subset S of the set \lbrace 1, 2, \ldots, N \rbrace is said to be a good set if:

  • for all i, j \in S, at least one of the following two conditions is satisfied:
    • the segment [L_i, R_i] contains the segment [L_j, R_j];
    • the segment [L_j, R_j] contains the segment [L_i, R_i].

Here, a segment [L, R] is said to contain another segment [L', R'] if and only if L \leq L' and R' \leq R.

Find the maximum possible size of a good set.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 0 \leq L_i < R_i \leq 10^9
  • All values in the input are integers.

Input

The input is given from Standard Input in the following format:

N
L_1 R_1
L_2 R_2
\vdots
L_N R_N

Output

Print the answer.

Sample Input 1

4
1 3
2 4
3 4
1 4

Sample Output 1

3

The set \lbrace 2, 3, 4 \rbrace is a good set with the maximum size. Actually,

  • for 2, 3 \in S, [L_2, R_2] contains [L_3, R_3];
  • for 2, 4 \in S, [L_4, R_4] contains [L_2, R_2]; and
  • for 3, 4 \in S, [L_4, R_4] contains [L_3, R_3];

so the size 3 should be printed.

Sample Input 2

3
0 1
0 1
0 1

Sample Output 2

3

Sample Input 3

9
1 6
1 3
3 6
4 6
2 5
1 2
3 4
3 5
2 7

Sample Output 3

4