Шары и коробки - 2
(Время: 1 сек. Память: 16 Мб Сложность: 68%)
По кругу стоит N коробок. Каждая коробка имеет одного правого и одного левого соседа. В i-ой коробке находится Ai шаров. Известно, что общее количество шаров во всех коробках не превосходит N. За один ход разрешается переложить один шар из коробки в соседнюю. Какое наименьшее количество ходов придется совершить, чтобы в каждой коробке находилось не более одного шара?
Входные данные
Первая строка входного файла INPUT.TXT содержит целое число N (1 ≤ N ≤ 1000). Во второй строке определена последовательность N целых чисел A1, A2, ... , AN (0 ≤ Ai ≤ N). Сумма всех значений Ai не превосходит N.
Выходные данные
В выходной файл OUTPUT.TXT выведите искомое минимальное количество ходов.
Пример
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 7
1 0 0 0 2 3 1 | 7 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 
