Rənglər Bayramı
Cənubi Amerikada səyahət edərkən, qəhrəmanlarımız Rənglər bayramının qeyd olunduğu Koloroviya dövlətinə gəldilər. Bayram münasibətilə sakinlər stadionun qaçış zolağında yarış keçirirdilər və bu zolaq əvvəlcədən müxtəlif rənglərlə boyanırdı. Boyama prosesində N rəssam iştirak edirdi və hər biri fərqli rənglə boyayırdı. Hər bir rəssam hansı qaçış zolağı hissəsini boyamalı olduğunu bilirdi. Lakin boyama prosesi ardıcıl olaraq həyata keçirildiyi üçün qaçış zolağının bəzi hissələri yenidən boyanırdı. Bir az düşündükdən sonra Kotıhoroshko rəssamların işini elə bir ardıcıllıqla təşkil etdi ki, boyama prosesi bitdikdən sonra zolaqda görünən rənglərin sayı maksimum olsun.
Siz də bunu etməyə çalışın.
Giriş verilənləri
Birinci sətir tam ədəd N (1 ≤ N ≤ 300) ehtiva edir. Növbəti N sətir hər biri iki tam ədəd ehtiva edir. Bu sətirlərin i-cisində L_{i} və R_{i} (–10^9 ≤ L_{i} < R_{i} ≤ 10^9) ədədləri yerləşir, burada L_{i} – i-ci hissənin boyanmasının başlanğıc koordinatıdır; R_{i} – i-ci hissənin boyanmasının son koordinatıdır.
Çıxış verilənləri
Birinci sətirdə optimal boyama ardıcıllığında zolaqda görünəcək maksimum rəng sayını çıxarmaq lazımdır.
İkinci sətirdə N ədəd yazılmalıdır – i-ci ədəd optimal nəticəyə nail olmaq üçün i-ci olaraq hansı hissənin boyanmalı olduğunu göstərir.
Hissələr, giriş faylında verildiyi ardıcıllıqla, birdən başlayaraq nömrələnir.
Qeyd. Bir neçə həll yolu varsa, onlardan hər hansı birini çıxarmaq olar.