Балансировка нагрузки
Процессоры многопроцессорной системы соединены в цепь последовательно, один за одним. Они пронумерованы целыми числами от 1 до n. Каждый из них содержит некоторый набор заданий на исполнение, i-ый процессор содержит t_i заданий. Система будет сбалансированной, если каждый процессор будет содержать одинаковое количество заданий. Балансировка нагрузки происходит раундами. Каждый раунд каждый процессор может "передать" не более одного задания каждому своему соседу. Соседями процессора i являются процессоры с номерами i-1 и i+1, крайние процессоры имеют лишь по одному соседу. Найдите наименьшее количество раундов, необходимое для балансировки системы.
Входные данные
В первой строке входного файла записано целое число n – количество процессоров (1 ≤ n ≤ 5000). Вторая строка содержит последовательность t. Последовательность имеет длину n и содержит целые числа, каждое из которых от 0 до 50000 включительно.
Выходные данные
Выведите наименьшее количество раундов, необходимое для балансировки системы. Если сумма значений последовательности t не кратна n, то решения не существует. В этом случае выведите -1.