ЛШКН

Вася хочет поехать преподавателям в Летнюю школу по компьютерным наукам (ЛШКН). Это его первый опыт преподавания, поэтому он хочет тщательно подготовить свои лекции по одной из тем.

В ЛШКН читаются по две лекции ежедневно, расписание лекций уже составлено на n дней. Тема лекции в каждый из дней обозначается целым числом от 1 до 5. Васю готовы пригласить на любое количество подряд идущих дней, с условием, что каждый день он будет читать лекцию по подготовленной им теме.

Помогите Васе выбрать тему для подготовки таким образом, чтобы максимизировать количество дней, проведенных в ЛШКН.

Формат входных данных
В первой строке вводится число n (1 ≤ n ≤ 100000).

В следующих n строках вводится по два числа ai, bi (1 ≤ ai, bi ≤ 5) - номера тем лекций в i-й день.

Формат результата
Выведите два числа: максимальное количество дней, которые Вася сможет провести в ЛШКН и номер темы, лекции по которой ему нужно подготовить. Если подходит несколько тем, то выведите тему с наименьшим номером.

Примеры
Входные данные
1
1 5
Результат работы
1 1
Входные данные
3
3 5
4 5
1 3
Результат работы
2 5
Входные данные
4
2 1
3 2
5 3
2 5
Результат работы
2 2
Примечания
В первом примере Вася может приехать на один день, подготовившись к темам 1 или 5. Он должен выбрать тему 1, т.к. ее номер меньше.

Во втором примере Вася может приехать на первый и второй день, подготовившись к теме 5. Он не может приехать на первый и третий день, подготовившись к теме 3, т.к. эти дни идут не подряд.

В третьем примере Вася приезжает на первый и второй день, подготовившись к теме 2. Он не может остаться на четвертый день с этой же темой, т.к. дни, когда он читает лекции, должны идти подряд, а в третий день лекции с темой 2 нет. Также он не может остаться на два дня (третий и четвертый) с темой 5, т.к. 5 больше 2 и следует выбирать тему 2.

Система оценки:

Решения, верно работающие при n ≤ 100 будут набирать не менее 70 баллов.

0

0

0