Задача 13 из 21

Пики посещаемости

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

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

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

Определите, сколько пиков посещаемости было в течение суток, и число посетителей в момент пика.

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

В первой строке находится число NN — количество посетителей магазина (натуральное число, меньшее 10 00010\,000). Каждая из следующих NN строк содержит два натуральных числа, не превышающих 1440: время входа и время выхода посетителя; время входа не больше времени выхода.

Посетители записаны в произвольном порядке; одинаковые пары чисел возможны.

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

Выведите два целых числа: сначала количество пиков посещаемости, затем число посетителей в момент пика.

Примеры

Ввод 1
6
10 50
100 150
110 155
120 160
130 170
151 170
Вывод 1
2 4
Ввод 2
2
1 2
2 3
Вывод 2
1 2

Примечание

В первом примере максимум равен четырём посетителям. Он достигается на отрезках [130; 150] и [151; 155]. Между моментами 150 и 151 посетителей трое, поэтому это два отдельных пика. Во втором примере оба посетителя находятся в магазине только в общий момент 2: это один пик с двумя посетителями.

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

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

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