题目描述

老师准备了一堆糖果, 恰好 $n$ 个小朋友可以分到数目一样多的糖果. 老师要 $n$ 个小朋友去拿糖果, 然后围着圆桌坐好, 第1个小朋友的左边是第 $n$ 个小朋友, 其他第 $i$ 个小朋友左边是第 $i-1$ 个小朋友. 大家坐好后, 老师发现, 有些小朋友抢了很多的糖果, 有的小朋友只得到了一点点糖果, 甚至一颗也没有 , 设第 $i$ 个小朋友有 $a_i$ 颗糖果. 小朋友们可以选择将一些糖果给他左边的或者右边的小朋友, 通过”糖果传递”最后使得每个小朋友得到的糖果数是一样多的, 假设一颗糖果从一个小朋友传给另一个小朋友的代价是 $1$, 问怎样传递使得所耗的总代价最小.

输入格式

第一行一个正整数 $n$ ,表示小朋友的个数.

$n$ 行,每行一个整数 $a_i$,表示第 $i$ 个小朋友得到的糖果的颗数.

输出格式

输出只有一个数, 表示最小代价.

4                               
1
2
5
4

4

提示

数据范围 30%的测试数据, $n\leq 1000$.

100%的测试数据, $n\leq 1000000$，$a_i\geq 0$, 保证 $a_i$ 在longint/int范围内, $a_i$ 的总和在int64/long long范围内.