H - 温度管理 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

問題文

N 人の人が温泉に入りに来ました。i 番目の人は、 L_i 度以上 R_i 度以下の温度の温泉に入ることができると満足します。

あなたはどんな温度の温泉をいくつでも用意することができます。ただし、1 つの温泉は 1 つの温度にしか設定できません。

N 人全員が満足できるように温泉を用意するとき、用意する必要がある温泉の数の最小値を求めてください。

制約

  • 1 \leq N \leq 2 \times 10^{5}
  • 1 \leq L_i \leq R_i \leq 10^{9}
  • 入力は全て整数である。

入力

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

N
L_1 R_1
L_2 R_2
\vdots
L_N R_N

出力

用意する必要がある温泉の数の最小値を出力せよ。

入力例 1

5
37 40
43 45
40 42
35 39
39 43

出力例 1

3

39 度, 41 度, 45 度の 3 つの温泉を用意すれば、全員が満足することができます。2 つ以下の温泉を用意して全員が満足することはできません。よって、3 を出力します。

入力例 2

7
27 50
40 43
55 60
25 30
33 49
35 39
32 45

出力例 2

4

Problem Statement

N people came to use a hot spring. The i-th person will be satisfied if they bathe in a hot spring with temperature between L_i and R_i degrees, inclusive.

You can prepare any number of hot springs at any temperature. However, each hot spring can have only one set temperature.

At least how many hot springs do you need to prepare so that all the N people are satisfied?

Constraints

  • 1 \leq N \leq 2 \times 10^{5}
  • 1 \leq L_i \leq R_i \leq 10^{9}
  • All input values 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 minimum number of hot springs you need to prepare.

Sample Input 1

5
37 40
43 45
40 42
35 39
39 43

Sample Output 1

3

If you prepare three hot springs at 39, 41, and 45 degrees, everyone will be satisfied. However, you can never satisfy everyone by preparing two hot springs or less. Thus, 3 should be printed.

Sample Input 2

7
27 50
40 43
55 60
25 30
33 49
35 39
32 45

Sample Output 2

4