Балансування навантаження#2092
У багатопроцесорній системі процесори з'єднані в послідовний ланцюг і пронумеровані від до . Кожен процесор має певну кількість задач, що позначається як t_i. Система вважається збалансованою, якщо кожен процесор має однакову кількість задач. Балансування навантаження виконується раундами. У кожному раунді кожен процесор може передати не більше однієї задачі кожному зі своїх сусідів. Сусідами процесора є процесори i-1 та i+1, а перший і останній процесори мають лише одного сусіда. Знайдіть мінімальну кількість раундів, необхідних для балансування системи.
Перший рядок містить ціле число (1 \le n \le 5000) — кількість процесорів. Другий рядок містить послідовність довжини , де кожен елемент — це ціле число від до включно.
Виведіть мінімальну кількість раундів, необхідних для балансування системи. Якщо сума послідовності не ділиться на , рішення не існує. У цьому випадку виведіть -1.
Приклад 1