Задача №113585. Мульти-музыкант
Юная Мирка - начинающий музыкант. Она играет на мульти-пианино. Мульти-пианино имеет бесконечно много мульти-клавиш, обозначенных целыми числами, которые можно воспринимать как ноты. Мульти-композиция (композиция для мульти-пианино) может быть представлено как последовательность чисел, обозначающих мульти-клавиши, которые должны быть нажаты (то есть ноты, которые должны быть сыграны).
Мирка услышала на мульти-радио мульти-композицию, и теперь она хочет сыграть ее. К сожалению, она не не умеет точно узнавать ноты по звуку, но может понимать, была ли нота с радио выше или ниже последней сыгранной ей ноты. Поэтому, она решила сыграть мульти-композицию следующим образом:
1. Перед началом игры, она выберет целое неотрицательное число K .
2. В начале, она сыграет правильную ноту (ее мульти-учитель сказал ей, какую клавишу нужно нажать первой)
3. Когда она услышит ноту выше, чем она только что сыграла, она будет нажимать на мульти-клавишу с числом на K больше, чем она только что сыграла.
4. Когда она услышит ноту ниже, чем она только что сыграла, она будет нажимать на мульти-клавишу с числом на K меньше, чем она только что сыграла.
5. Когда она услышит такую же ноту, как только что сыграла, она будет нажимать на ту же мульти-клавишу, что только что сыграла.
Помогите Мирке выбрать такое K , чтобы она правильно сыграла как можно больше нот мульти-композиции.
Первая строка содержит одно целое число N ( 2 ≤ N ≤ 10 6 ) - количество нот в мульти-композиции. Вторая строка содержит N целых чисел a i ( - 10 9 ≤ a i ≤ 10 9 ) - ноты мульти-композиции.
В первой строке выведите одно целое число - максимальное количество нот, которое Мирка может сыграть правильно. Во второй строке выведите одно неотрицательное целое число - значение K ( 0 ≤ K ≤ 10 9 ), которое должна выбрать Мирка, чтобы сыграть правильно максимальное количество нот. Если существует несколько решений, выведите любое.
5 1 2 0 3 1
3 2
7 2 1 -6 -2 1 6 10
5 4