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

Древние цивилизации

Древние цивилизации

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

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

Петя предположил, что между цивилизациями A и B происходил культурный обмен, если они сосуществовали в течении некоторого ненулевого промежутка времени. Например, если цивилизация A зародилась в 600 году до н.э. и существовала до 400 года до н.э., а цивилизация B зародилась в 450 году до н.э. и существовала до 300 года до н.э., то культура каждой из этих цивилизаций оказывала влияние на развитие другой цивилизации в течении 50 лет. В то же время, если цивилизация C зародилась в 400 году до н.э. и существовала до 50 года до н.э., то она не смогла осуществить культурного обмена с цивилизацией A, в то время как культурный обмен с цивилизацией B продолжался в течении 100 лет.

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

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

Первая строка входного файла содержит число N - количество цивилизаций, культура которых интересует Петю (1 N100000). Следующие N строк содержат описание цивилизаций - каждая строка содержит пару целых чисел S_i и E_i - год зарождения и год гибели соответствующей цивилизации. Все числа не превосходят 10^9 по абсолютной величине, S_i < E_i.

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

Выведите два числа - номера цивилизаций, периоды существования которых имеют наименьшее ненулевое пересечение. Если никакие две цивилизации не пересекаются во времени, выведите в выходной файл единственное число 0.

Пример

Входные данные #1
3
-600 -400
-450 -300
-400 -50
Выходные данные #1
1 2
Автор Сергей Оршанский