問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう!
paiza スキルチェックでは年に何度かキャンペーンを開催しています。各回ではキャンペーン問題が提供され、その問題を解くと抽選で商品がもらえます。また、キャンペーンは n 回開催され、 i 回目のキャンペーンは paiza サービス開始日から数えて、 l_i 日目から r_i 日目の間(l_i 日目、 r_i 日目を含む)に開催される予定です。
多くの商品がほしい京子ちゃんはできるだけ多くのキャンペーンに参加したいと思っています。しかし、京子ちゃんにとってキャンペーン問題は非常に難しく、開催期間中はずっとその問題に取りかかるため、 2 つの問題を同時に考えることはできません。このとき、京子ちゃんは最大でいくつのキャンペーンに参加できますか?
たとえば、 n = 3, l = [ 1, 4, 7 ], r = [ 4, 7, 10 ]の場合、以下の画像のようにキャンペーンが開催されています。
このときは最大でキャンペーン 1 とキャンペーン 3 の 2 つに参加できます。別のサンプルも見てみましょう。 n = 3, l = [ 1, 3, 6 ], r = [ 8, 5, 9 ] の場合も 2 つのキャンペーン (キャンペーン 2 とキャンペーン 3) に参加できます。
n
l_1 r_1
l_2 r_2
...
l_n r_n
京子ちゃんが参加できる最大のキャンペーンの個数を答えてください。
また、末尾に改行を入れ、余計な文字、空行を含んではいけません。
すべてのテストケースにおいて、以下の条件をみたします。
・ 1 ≦ n ≦ 100,000
・ 1 ≦ l_i ≦ r_i ≦ 200,000
3
1 4
4 7
7 10
2
3
1 8
3 5
6 9
2