eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Отрезки

Отрезки

Лимит времени 1 секунда
Лимит использования памяти 128 MiB

Даны отрезки на прямой. Какое максимальное количество отрезков можно выбрать так, чтобы никакие два из них не пересекались? Отрезки считаются открытыми.

Входные данные

В первой строке задано количество отрезков n~(1 \le n \le 10^5). В следующих n строках описаны отрезки: i-ая строка содержит два целых числа l_i и r_i~(1 \le l_i < r_i \le 10^9) — координаты начала и конца отрезка.

Выходные данные

Выведите максимальное количество непересекающихся отрезков.

Пример

Входные данные #1
5
1 4
3 8
7 8
2 5
4 6
Выходные данные #1
3
Входные данные #2
4
1 3
2 6
1 8
2 5
Выходные данные #2
1