1314. [HAOI 2008]糖果传递

【题目描述】

老师准备了一堆糖果，恰好 $n$ 个小朋友可以分到数目一样多的糖果．老师要 $n$ 个小朋友去拿糖果，然后围着圆桌坐好，第 $1$ 个小朋友的左边是第 $n$ 个小朋友其他第 $i$ 个小朋友左边是第 $i-1$ 个小朋友。大家坐好后，老师发现，有些小朋友抢了很多的糖果，有的小朋友只得到了一点点糖果，甚至一颗也没有，设第 $a_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$ 在长整型范围内， $a_i$ 的总和在 $int64/long$ $long$ 范围内．

【来源】

$HAOI$