Задача 16 из 21

Рейтинг продуктов

Время 2 с · память 256 МБ

Отдел маркетинга составляет рейтинг NN продуктов. Для каждого продукта известны срок хранения с момента изготовления и срок годности после вскрытия упаковки. Продукты пронумерованы начиная с единицы в том порядке, в каком они записаны во входных данных.

Места в рейтинге распределяют так. Все 2N2N чисел, обозначающих сроки, просматривают в порядке возрастания. Если очередное число относится к продукту, который уже занял место, его не принимают во внимание. Если очередное число — срок хранения с момента изготовления, продукт занимает первое свободное место от начала рейтинга; если это срок годности после вскрытия упаковки — первое свободное место от конца рейтинга.

Определите номер продукта, который займёт своё место в рейтинге последним, и количество продуктов, которые займут в рейтинге более низкие места. Чем ближе место к началу рейтинга, тем оно выше.

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

В первой строке находится число NN — количество продуктов (натуральное число, не превышающее 1000). Каждая из следующих NN строк содержит два натуральных числа, не превышающих 10910^9: срок хранения продукта с момента изготовления и срок годности после вскрытия упаковки.

Все 2N2N чисел различны.

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

Выведите два целых числа: сначала номер продукта, который займёт своё место в рейтинге последним, затем количество продуктов, которые займут более низкие места.

Примеры

Ввод 1
5
30 50
100 155
150 170
10 160
120 55
Вывод 1
3 1
Ввод 2
3
9 1
2 8
7 3
Вывод 2
3 1

Примечание

В первом примере итоговый рейтинг: 4, 1, 2, 3, 5. Последним размещён продукт 3; ниже него находится один продукт. Во втором примере рейтинг: 2, 3, 1. Последним размещён продукт 3; ниже него один продукт.

Решение
Загрузка редактора…
Результат появится здесь

Черновик сохраняется в этом браузере.

Ошибка в задаче