Circular Warehouse Balancing

The problem involves n warehouses arranged on a circle along a railway. Each warehouse \(i\) stores \(a_i\) units of goods. The goal is to make the inventory of all warehouses equal by transporting goods only between adjacent warehouses. In one move, goods can be transferred between two directly adjacent warehouses (note that the first and the last warehouse are also adjacent as the warehouses form a circle).

Let \(S = \sum_{i=0}^{n-1} a_i\) be the total amount of goods, so the target number of goods in each warehouse is \(T = \frac{S}{n}\). Define the difference \(d_i = a_i - T\) for each warehouse. Choose a starting point and let the prefix sum be defined as

[ F_k = \sum_{i=0}^{k-1} d_i, \quad k=1,2,\dots,n ]

Because the warehouses form a circle, \(F_n=0\). It can be shown that the minimum total amount of goods that must be moved is given by

[ \text{Answer} = \sum_{k=1}^{n} \left| F_k - m \right| ]

where (m) is the median of the sequence ({F_1, F_2, \dots, F_n}). Your task is to compute this minimum total transported load.

inputFormat

The first line contains a single integer \(n\) (the number of warehouses). The second line contains \(n\) space-separated integers \(a_0, a_1, \dots, a_{n-1}\), where \(a_i\) denotes the number of goods in the \(i\)-th warehouse. It is guaranteed that \(S = \sum_{i=0}^{n-1} a_i\) is divisible by \(n\).

outputFormat

Output a single integer, representing the minimum total amount of goods to be moved to equalize all warehouse inventories.

sample

3
1 2 3

1