eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Балансировка нагрузки

Балансировка нагрузки

Ліміт часу 4 секунди
Ліміт використання пам'яті 64 MiB

Процессоры многопроцессорной системы соединены в цепь последовательно, один за одним. Они пронумерованы целыми числами от 1 до n. Каждый из них содержит некоторый набор заданий на исполнение, i-ый процессор содержит t_i заданий. Система будет сбалансированной, если каждый процессор будет содержать одинаковое количество заданий. Балансировка нагрузки происходит раундами. Каждый раунд каждый процессор может "передать" не более одного задания каждому своему соседу. Соседями процессора i являются процессоры с номерами i-1 и i+1, крайние процессоры имеют лишь по одному соседу. Найдите наименьшее количество раундов, необходимое для балансировки системы.

Вхідні дані

В первой строке входного файла записано целое число n – количество процессоров (1n5000). Вторая строка содержит последовательность t. Последовательность имеет длину n и содержит целые числа, каждое из которых от 0 до 50000 включительно.

Вихідні дані

Выведите наименьшее количество раундов, необходимое для балансировки системы. Если сумма значений последовательности t не кратна n, то решения не существует. В этом случае выведите -1.

Приклад

Вхідні дані #1
4
0 3 0 1
Вихідні дані #1
1