Поиск

Бассейн


Ограничение времени               1.3 секунды
Ограничение памяти 64Mb
Ввод стандартный ввод или input.txt
Вывод стандартный вывод или output.txt

В бассейне плавают S человек. Тренер обнаружил, что они распределились по дорожкам крайне неравномерно, что создает неудобство многим посетителям бассейна. Но смена дорожки влечет за собой неудобство - перелезание через разделительный элемент.

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

Формат ввода

В первой строке входного файла находится число N — количество дорожек соответственно, 1 ≤ N ≤ 400. В следующей строке через пробел расположены N чисел, количество пловцов на первой, второй, . . . , N-ой дорожках соответственно. Сумма этих чисел равна S (0 ≤ S ≤ 1500).

Формат вывода

Выведите минимально возможное суммарное число пересечений барьеров, за которое можно перераспределить пловцов по дорожкам требуемым образом

Пример 1

Ввод

3
8 0 2

Вывод

5

Пример 2

Ввод

3
8 5 7

Вывод

1


Для отправки решения задачи необходимо авторизоваться!