| Codeforces Round 415 (Div. 1) |
|---|
| Закончено |
Леха и Нура решили отправиться в путешествие по Прибалтике. Всего они хотели бы посетить n городов. Но оказалось, что достопримечательности в i-м городе доступны для посещения только в промежуток дней с li по ri.
Что же делать? Леха предложил выбрать для каждого города i день, в который они посетят этот город, то есть целое число xi, принадлежащее промежутку [li, ri]. После этого Нура должна выбрать некоторую последовательность городов, в которые поедут друзья, то есть такие номера городов id1, id2, ..., idk, что, во-первых, они идут в строго возрастающем порядке idi < idi + 1 для всех целых i от 1 до k - 1, а, во-вторых, для выбранных Нурой городов дни посещения также находятся в строго возрастающем порядке, то есть должно выполняться xidi < xidi + 1 для всех целых i от 1 до k - 1.
Помогите Лехе и Нуре выбрать такие xi для каждого города i, а также некоторую последовательность городов id1, id2, ..., idk так, чтобы они смогли посетить как можно больше городов!
Следует полагать, что Леха и Нура готовы начать путешествие в любой день.
В первой строке входного файла задано одно целое число n (1 ≤ n ≤ 3·105) — количество городов, которые планировали посетить Леха и Нура.
Каждая строка i из следующих n строк содержит два целых числа li, ri (1 ≤ li ≤ ri ≤ 109), означающие, что достопримечательности в i-м городе доступны для посещения в любой день 
.
Выведите одно число — максимальное количество городов, которое могут посетить Леха и Нура.
5
6 6
1 2
3 4
2 2
1 4
3
Рассмотрим первый пример.
Возьмем следующий план: посетим достопримечательность во втором городе в первый день, в третьем городе — в третий день, а в пятом городе — в четвертый. Это и будет оптимальным ответом.
