EduBrick

I. Стопки вложенных отрезков

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

Даны nn попарно различных отрезков. Отрезок AA можно положить внутрь отрезка BB, если AA лежит строго внутри BB: lB<lAl_B < l_A и rA<rBr_A < r_B. В одну стопку складывают отрезки, каждый следующий из которых вложен в предыдущий.

Нужно найти минимальное число стопок, на которые можно разложить все отрезки.

Формат ввода

В первой строке nn (1≤n≤10001 \le n \le 1000). В следующих nn строках по два числа lil_i и rir_i (1≤li<ri≤1091 \le l_i < r_i \le 10^9). Отрезки попарно различны.

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

Выведите минимальное количество стопок.

Примеры

ввод
4
1 10
2 9
3 4
11 12
вывод
2
ввод
1
1 2
вывод
1
Разбор идеи от автора задачи. Сначала попробуйте сами.
Войдите, чтобы отправлять решения.