D. Автостопом по Прибалтике
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Леха и Нура решили отправиться в путешествие по Прибалтике. Всего они хотели бы посетить 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
Примечание

Рассмотрим первый пример.

Возьмем следующий план: посетим достопримечательность во втором городе в первый день, в третьем городе — в третий день, а в пятом городе — в четвертый. Это и будет оптимальным ответом.