活動選択問題

$n$ 個の活動があります。$i$ 番目の活動は時刻 $s_i$ に始まり、時刻 $t_i$ に終了します。ある活動に参加した場合、その活動と活動時刻の被っている他の活動に参加することはできません。開始時刻と終了時刻のみが被るような場合も参加できないことに注意してください。

あなたはできるだけ多くの活動に参加したいと考えています。活動時刻の被っていないいくつかの活動を最適に選んだ時、最大で何個の活動に参加できるか求めてください。

入力

$n$
$s_1$ $t_1$
$s_2$ $t_2$
:
$s_n$ $t_n$

1行目に活動の数を表す整数 $n$ が与えられます。2行目以降の $n$ 行に、各活動の開始時刻と終了時刻を表す2つの整数 $s_i, t_i$ が空白区切で与えられます。

出力

参加できる活動の最大数を1行に出力してください。

制約

• $1 \le n \le 10^5$
• $1 \le s_i \lt t_i \le 10^9 (1 \le i \le n)$

入力例 1

5
1 2
3 9
3 5
5 9
6 8

出力例 1

3

入力例 2

3
1 5
3 4
2 5

出力例 2

1

入力例 3

3
1 2
2 3
3 4

出力例 3

2

---