Find Minimum Cost

n containers form a ring, and all products must end up evenly distributed among the containers; the total is guaranteed to be divisible by n. Moving one product across one adjacent edge costs 1. The whole process may use only one direction, clockwise or counterclockwise; either direction may be chosen, but they cannot be mixed. Find the minimum cost.

输入格式

The first line contains n; the second line contains the product counts. This site uses 1≤n≤200000, counts 0..10^9, and a total divisible by n.

输出格式

Output a single integer, the answer.

样例 1

输入：

5
3 4 6 6 6

输出：

7

样例 2

输入：

2
1 1

输出：

0

样例 3

输入：

2
0 2

输出：

1

样例说明

Example 1: the prefix surpluses are −2, −3, −2, −1, 0; the clockwise cost is 7 and the counterclockwise cost is 8, so the answer is 7. Example 2: already evenly distributed, cost 0. Example 3: send 1 product across one edge to the empty container, cost 1.