Акция
(Время: 2 сек. Память: 16 Мб Сложность: 48%)
Сегодня в городе N начинает свою работу новый оператор связи LiteLife. Он открывает сразу n офисов в городе. Так как только дешевыми тарифами и 6G-интернетом уже не привлечь много клиентов, руководство LiteLife решило устроить акцию. Условия акции таковы: если клиент будет находиться в i-том офисе компании с момента времени li по момент времени ri включительно, он получит 200 бонусов на свой счет.
Серёжа, конечно, не смог пропустить эту интересную акцию. Он сразу понял, что можно несколько раз получить бонусы, посетив несколько офисов LiteLife. Известно, что любимый тариф Серёжи называется «Самый безлимитный», его стоимость – как раз 200 бонусов в месяц. Для того, чтобы получить как можно больше бонусов (а, следовательно, бесплатных месяцев использования «Самого безлимитного» тарифа), Сережа изобрёл телепорт, позволяющий мгновенно перемещаться между двумя любыми офисами LiteLife.
Помогите Серёже выбрать такой порядок посещения офисов, что он получит как можно больше бонусов!
Входные данные
В первой строке входного файла INPUT.TXT записано натуральное число n (1 ≤ n ≤ 100000) - количество офисов.
В каждой из n последующих строк вводится пара натуральных чисел li и ri (1 ≤ li ≤ ri ≤ 109) – период проведения акции в очередном офисе LiteLife.
Выходные данные
В первую строку выходного файла OUTPUT.TXT нужно вывести одно натуральное число k – максимально возможное число офисов, в которых Серёжа получит бонусы. Во второй строке выведите k натуральных чисел – номера офисов, которые должен посетить Серёжа. Офисы нумеруются с единицы в порядке их следования во входных данных. Найденные номера выводить в порядке посещения офисов. Если существует несколько способов посещения офисов, то вывести любой из них.
Примеры
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 2
1 2
3 4 | 2
1 2
|
| 2 | 5
5 8
4 7
3 6
2 5
1 4 | 2
5 1 |
Пояснения к примерам
В первом примере Серёжа может посетить оба офиса по очереди, получив 400 бонусов. Во втором примере Серёжа с момента времени 1 по момент 4 должен находиться в пятом офисе, получить бонус и телепортироваться в первый офис, чтобы находиться там с момента 5 по момент 8. Это единственный способ получить два бесплатных месяца использования «Самого безлимитного» тарифа.
Система оценки
Решения, работающие для n, li, ri ≤ 1000, оцениваются в 50 баллов.
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 
