糖果传递

老师准备了一堆糖果，这些糖果恰好可以平均分给 $n$ 个小朋友。老师让这 $n$ 个小朋友取走糖果，然后围着圆桌坐好。第 $1$ 个小朋友的左边是第 $n$ 个小朋友，其余第 $i$ 个小朋友的左边是第 $i-1$ 个小朋友。

坐好后，老师发现小朋友们拿到的糖果数量并不均匀：有些小朋友拿到了很多糖果，有些小朋友只拿到了一点，甚至一颗也没有。设第 $i$ 个小朋友有 $a_i$ 颗糖果。

每个小朋友都可以将一些糖果传给左边或右边的小朋友。通过若干次“糖果传递”，最终使每个小朋友拥有的糖果数量相同。将一颗糖果从一个小朋友传给相邻小朋友的代价为 $1$。

请计算使所有小朋友拥有相同数量的糖果所需的最小总代价。

输入格式

第一行包含一个正整数 $n$，表示小朋友的数量。

接下来 $n$ 行，每行包含一个整数 $a_i$，表示第 $i$ 个小朋友拥有的糖果数量。

输出格式

输出一个整数，表示最小总代价。

样例输入

4
1
2
5
4

样例输出

4

数据范围

• 对于 $30\%$ 的测试数据，$n\le 1000$；
• 对于 $100\%$ 的测试数据，$n\le 10^6$；
• $a_i\ge 0$，且 $a_i$ 在 longint 或 int 的表示范围内；
• 所有 $a_i$ 之和在 int64 或 long long 的表示范围内。

来源与许可

本题题面与测试数据整理自 BZOJ。

样例 1

输入

4
1
2
5
4

输出

4