Леха и Нура решили отправиться в путешествие по Прибалтике. Всего они хотели бы посетить n городов. Но оказалось, что достопримечательности в i-м городе доступны для посещения только в промежуток дней с li по ri.
Что же делать? Леха предложил выбрать для каждого города i день, в который они посетят этот город, то есть целое число xi, принадлежащее промежутку [li, ri]. После этого Нура должна выбрать некоторую последовательность городов, в которые поедут друзья, то есть такие номера городов id1, id2, ..., idk, что, во-первых, они идут в строго возрастающем порядке idi < idi + 1 для всех целых i от 1 до k - 1, а, во-вторых, для выбранных Нурой городов дни посещения также находятся в строго возрастающем порядке, то есть должно выполняться xidi < xidi + 1 для всех целых i от 1 до k - 1.
Помогите Лехе и Нуре выбрать такие xi для каждого города i, а также некоторую последовательность городов id1, id2, ..., idk так, чтобы они смогли посетить как можно больше городов!
Следует полагать, что Леха и Нура готовы начать путешествие в любой день.
Примечание
Рассмотрим первый пример.
Возьмем следующий план: посетим достопримечательность во втором городе в первый день, в третьем городе — в третий день, а в пятом городе — в четвертый. Это и будет оптимальным ответом.