У Левко есть массив, состоящий из целых чисел: a1, a2, ... , an. Но этот массив совсем ему не нравится.
Левко считает, что красота массива a напрямую зависит от значения c(a), которое можно посчитать по формуле:
Чем значение
c(a) меньше, тем массив красивее.
Наступило время перемен, и Левко собирается изменить свой массив к лучшему. Если быть точнее, Левко хочет изменить значения не более k элементов массива (разрешается изменять значения на любые целые). Конечно, в результате изменений массив должен стать как можно более красивым.
Помогите Левко — посчитайте, какого минимального значения c(a) ему удастся достичь.
Примечание
В первом примере Левко может изменить второй и четвертый элементы и получить массив: 4, 4, 4, 4, 4.
В третьем примере он может получить массив: 1, 2, 3, 4, 5, 6.