D. Физкультура и булочки
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Учитель физкультуры СУНЦа тоже немного математик. Больше всего в математике он любит арифметические прогрессии. Именно поэтому учитель хочет, чтобы ученики, выстроенные по неубыванию роста, образовывали арифметическую прогрессию.

Для достижения своей цели учитель физкультуры заказал очень много волшебных булочек из столовой. Волшебные булочки бывают двух типов: когда ученик съедает одну волшебную булочку первого типа, его рост увеличивается на единицу; когда ученик съедает одну волшебную булочку второго типа, его рост уменьшается на единицу. Учитель физкультуры, как и положено, заботится о здоровье своих учеников, поэтому не хочет, чтобы они ели очень много булочек. Точнее, он хочет, чтобы максимальное количество булочек, съеденных некоторым учеником, было минимально.

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

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

В первой строке содержится целое число n (2 ≤ n ≤ 103) — количество учеников. Во второй строке через пробел записаны n целых чисел — рост всех учеников. Рост одного ученика — это целое число, по модулю не превосходящее 104.

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

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

Если существует несколько верных ответов, разрешается вывести любой.

Примеры
Входные данные
5
-3 -4 -2 -3 3
Выходные данные
2
-3 1
Входные данные
5
2 -3 -1 -4 3
Выходные данные
1
-4 2
Примечание

В первом тестовом примере учителю нужно действовать следующим способом:

  • не кормить 1-го ученика, его рост останется равным -3;
  • накормить 2-го ученика двумя булочками первого типа, его рост станет равным -2;
  • накормить 3-го ученика двумя булочками первого типа, его рост станет равным 0;
  • накормить 4-го ученика двумя булочками первого типа, его рост станет равным -1;
  • накормить 5-го ученика двумя булочками второго типа, его рост станет равным 1.

Итого, когда ученики встанут в шеренгу по неубыванию роста получится прогрессия: -3, -2, -1, 0, 1. Минимальный рост ученика в прогрессии равен -3, шаг прогрессии равен 1. Ученик, который съел больше всего булочек, съел две булочки. То есть максимальное количество булочек, съеденных одним учеником равно 2.