Задание №26

Альпинист планирует маршрут, проходящий через несколько горных лагерей. Каждый лагерь характеризуется своей высотой над уровнем моря. Из одного лагеря можно перейти в другой, если высота второго лагеря меньше высоты первого не более чем на 38 метров. Альпинист может не более двенадцати раз за весь маршрут воспользоваться страховочной системой, позволяющей выполнить переход, при котором высота второго лагеря меньше высоты первого не более чем на 70 метров. Каждый лагерь может быть посещён не более одного раза. Маршрут может быть начат в любом из лагерей и считается завершённым, если из текущего лагеря невозможно выполнить допустимый переход ни обычным способом, ни с использованием страховочной системы.

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

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

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

Типовой пример организации данных во входном файле
6
20
12
15
8
10
5

Пример входного файла приведён для шести горных лагерей. Минимальная допустимая разница для обычного перехода составляет 3 метра, при этом один раз разрешён переход до 6 метров с использованием страховочной системы. При этих данных маршрут с максимальным количеством лагерей включает 6 лагерей с высотами 20, 15, 12, 10, 8, 5, а высота завершающего лагеря равна 5. Спец-переход использован один раз $(20\to 15)$.

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