Load balancing#2092
In a multiprocessor system, the processors are connected in a sequential chain and numbered from to . Each processor has a certain number of tasks, denoted as t_i. The system is considered balanced if each processor has the same number of tasks. Load balancing is performed in rounds. In each round, every processor may transfer at most one task to each of its neighbors. The neighbors of processor are processors i-1 and i+1, while the first and last processors have only one neighbor each. Find the minimum number of rounds required to balance the system.
The first line contains an integer (1 \le n \le 5000), the number of processors. The second line contains a sequence of length , where each element is an integer between and inclusive.
Print the minimum number of rounds required to balance the system. If the sum of the sequence is not divisible by , there is no solution. In this case, print -1.
Example 1