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