Задание 26 из ЕГЭ по информатике: задача 5

На новогодней фабрике подарков Деда Мороза составляют рейтинговый список новых видов подарков по данным о времени изготовления игрушки в обычном режиме и в ускоренном предпраздничном режиме. У каждого подарка известны оба показателя. Названия подарков скрыты, все подарки пронумерованы начиная с 1.

Алгоритм формирования рейтинга:

• все 2N чисел, обозначающих время изготовления в обычном режиме и в ускоренном режиме для N подарков, располагаются по возрастанию;
• если наименьший показатель соответствует времени изготовления в обычном режиме, подарок занимает первое свободное место от начала рейтинга;
• если наименьший показатель относится ко времени изготовления в ускоренном предпраздничном режиме, подарок занимает первое свободное место от конца рейтинга;
• показатели подарков, ранее включённых в рейтинговый список, игнорируются.

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

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

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

В первой строке входного файла находится натуральное число N (N ≤ 1000) — количество подарков.

Следующие N строк содержат пары натуральных различных чисел, обозначающих соответственно время изготовления подарка в обычном режиме и в ускоренном предпраздничном режиме.

Типовой пример входных данных

5
800 120
150 200
250 300
60 100
180 220

Пример приведён для пяти новогодних подарков.