EduBrick

Проколоть все отрезки

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

На прямой нарисовано nn отрезков. Нужно отметить несколько точек так, чтобы на каждом отрезке оказалась хотя бы одна отмеченная точка. Точка на конце отрезка считается принадлежащей ему.

Какое наименьшее число точек нужно отметить?

Формат ввода

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

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

Одно число.

Примеры

ввод
3
1 5 4 7 6 10
вывод
2

Примечание

Отрезок, который заканчивается раньше всех, придётся проколоть — и выгоднее всего сделать это в самом его конце.

Войдите, чтобы отправлять решения.