Minimize Warehouse Transfer Cost

n warehouses form a ring, and moving one item across an adjacent edge costs 1. The goal is for every warehouse to end up with the same number of items; the total is guaranteed to be divisible by n. The whole plan must use only one direction, either clockwise or counterclockwise, and cannot mix directions; you may choose any starting point. Find the minimum total cost.

输入格式

The first line contains n and the second line contains warehouses. On this site 1≤n≤200000, 0≤warehouses[i]≤10^9, and sum%n=0 is guaranteed. Output the exact integer cost, without any modulus.

输出格式

Output a single integer, the answer.

样例 1

输入：

4
0 4 4 0

输出：

8

样例 2

输入：

5
3 4 6 6 6

输出：

7

样例 3

输入：

2
1 1

输出：

0

样例说明

The answers are 8, 7 and 0 respectively. In the first example, moving items in both directions could cost 4, but the original rule of a single direction throughout makes the minimum 8.