Программирование – это искусство!
На вопрос слушателей Зимней Школы 2011: какая у него заработная плата, Пётр Митричев ответил очень политкорректно:
– По сравнению с L – много, а вот в сравнении с R – мало.
О том, кто же такие были эти загадочные L и R, Пётр дипломатично умолчал…
Задумываясь над тем, что бы такого интересного рассказать слушателям Зимней Школы 2011 в г. Харькове, Пётр усиленно перебирал возможные варианты тематики, но практически сразу их отбрасывал, так как темы всегда приходили на ум уже давно известные и кем-то ранее рассказанные. Но как истинный художник-программист, свободно владеющий фигурами высшего пилотажа в этом деле, он не мог себе позволить выбрать какую-то ординарную тему.
А расскажу я им об L и R – тем более, что об этом, кажется, ещё никто не рассказывал, – подумал Пётр и начал рисовать план лекции и набрасывать схемы задачек. Благо в фирме, где он работал, был большой запас маркеров разных цветов, и схемы он начал рисовать именно ими. Если ему что-то в схеме не нравилось, Пётр поступал очень просто: он брал маркер другого цвета и зарисовывал им непонравившееся ему месту сверху новым цветом, соответствующему новому пункту плана.
Перерисовывая таким образом схему, он очень быстро заметил, что и этот процесс можно предложить в виде задачки.
Некий программист использует для рисования на координатной прямой N отрезков N маркеров разных цветов. Зная левые (L) и правые (R) концы каждого нарисованного отрезка, определить максимальное количество разных цветов, которые можно получить в окончательном варианте рисунка. Это количество назовём уровнем этого художника-программиста.
Входные данные
В первой строке входного файла задано натуральное число N (1 ≤ N ≤ 300). В последующих N строках задано N пар чисел L и R через пробел (-10^9 ≤ L_i < R_i ≤ 10^9).
Выходные данные
Вывести единственное число: искомый наибольший уровень художника-программиста.