Description

Company G has $n$ warehouses arranged in a ring along a railway transport line. The amount of goods stored in each warehouse is not necessarily the same. What is the minimum total amount of goods that must be moved to make the inventories of the $n$ warehouses equal? When moving goods, you may only transfer goods between adjacent warehouses.

Input Format

The first line contains a positive integer $n$, denoting there are $n$ warehouses. The second line contains $n$ positive integers, denoting the inventory of the $n$ warehouses.

Output Format

Output a single non-negative integer on one line, the minimum total amount of goods to move.

5
17 9 14 16 4

11

Hint

$1 \leq n \leq 100, 1 \leq a_i \leq 100$, and it is guaranteed that $\sum a_i$ is a multiple of $n$.

Translated by ChatGPT 5