26_0368

Система наблюдения ежеминутно фиксирует вход и выход сотрудников из офиса (в минутах, прошедших от начала суток). Считается, что в моменты фиксации входа и выхода сотрудник находится в офисе. Нулевая минута соответствует моменту начала рабочего дня в офисе, который работает 24 ч в сутки без перерыва.

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

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

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

В первой строке входного файла находится натуральное число N (N ≤ 100 000) – количество сотрудников компании. Следующие N строк содержат пары чисел, обозначающих соответственно время входа и время выхода сотрудника (все числа натуральные, не превышающие 1440).

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

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

Типовой пример организации данных во входном файле

5
10 100
101 200
150 400
401 500
500 900

При таких исходных данных в течение суток было 7 промежутков времени, когда число сотрудников не менялось: (0, 10), (10, 150), (150, 201), (201, 500), (500, 501), (501, 901), (901, 1440). Наибольшей длиной из этих отрезков является число 539. В 501 минуту в предпоследний раз изменилось число сотрудников. Заметим, что в 101 минуту один сотрудник ушёл, а другой пришёл, поэтому число сотрудников не изменилось: сотрудник, вышедший в 100-ю минуту, находился в офисе в течение этой минуты.

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.

Файлы к заданию:

• 26_0368.txt