eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Голодный ферзь

Голодный ферзь

Лимит времени 1 секунда
Лимит использования памяти 64 MiB

Рассмотрим бесконечную шахматную доску, поля на которой задаются парами чисел: (x, y). Чёрный ферзь исходно находится на поле (0, 0). Ферзь может перемещаться по горизонтали, вертикали и диагонали, но при этом не может перемещаться вниз. А именно после каждого хода y-координата поля, на котором он находится, должна быть больше или равна y-координаты поля, на котором он был перед этим ходом.

На доске также находится n белых пешек, они располагаются в полях с координатами (x_i, y_i), где y_i > 0.

Ферзь хочет взять как можно больше пешек. Белые пешки не перемещаются, и ферзь может сделать столько последовательных ходов, сколько требуется. Однако в результате каждого хода ферзь должен брать пешку. Перепрыгивать через пешку не разрешается.

Выясните, какое максимальное количество пешек ферзь может взять, и какие пешки в каком порядке требуется брать.

Входные данные

Первая строка входного файла содержит n - количество пешек (1n50000). Следующие n строк содержат по два числа - координаты (x_i, y_i) пешек (|x_i| ≤ 10^9, 0 < y_i10^9). Никакие две пешки не находятся на одном и том же поле.

Выходные данные

Первая строка выходного файла должна содержать число k - количество пешек, которые может взять ферзь. Вторая строка должна содержать k целых чисел - номера пешек в том порядке, в котором их следует брать. Пешки нумеруются в том порядке, в каком они заданы во входном файле.

Пример

Входные данные #1
4
1 1
4 3
-1 3
4 2
Выходные данные #1
3
1 3 2