EduBrick

A. Расписание лектория

800 мс · 256 МБ · всё или ничего

В лекторий подано nn заявок. Заявка занимает зал с момента ss до момента ff: занятие идёт на промежутке [s;f)[s; f), поэтому следующая лекция может начаться ровно в момент ff — это не считается пересечением.

Зал один. Выберите как можно больше заявок так, чтобы никакие две выбранные не пересекались. Выведите, сколько лекций удастся провести.

Формат ввода

Первая строка содержит число nn (1≤n≤1051 \le n \le 10^5).

Следующие nn строк содержат по два целых числа ss и ff (0≤s<f≤1090 \le s < f \le 10^9).

Формат вывода

Одно число — наибольшее количество непересекающихся заявок.

Примеры

ввод
1
5 10
вывод
1
ввод
3
1 5
2 3
3 4
вывод
2
Войдите, чтобы отправлять решения.