EduBrick
← вернуться к уроку · Итоговый контест: второй тур

Расписание переговорной

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

На переговорную подано nn заявок, каждая занимает промежуток времени от lil_i до rir_i. Две заявки нельзя удовлетворить вместе, если их промежутки пересекаются; касание концами тоже считается пересечением.

Какое наибольшее количество заявок можно удовлетворить?

Формат ввода

В первой строке число nn от 11 до 21052 \cdot 10^5. Во второй — 2n2n чисел: пары ll и rr подряд, 1lr1091 \le l \le r \le 10^9.

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

Одно число.

Примеры

ввод
1
1 2
вывод
1
Войдите, чтобы отправлять решения.
← Вернуться к уроку