题目描述

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

输入格式

输入文件第一行一个正整数 n ，表示小朋友的个数。 接下来 n 行，每行一个整数ai，表示第i个小朋友得到的糖果的颗数。

输出格式

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

样例

4
1
2
5
4

4

数据范围与提示

样例解释 设四个人编号为 1,2,3,4。第 3 个人给第 2 个人 2 个金币（变成1 , 4 , 3 , 4 ），第 2 个人和第 4 个人分别给第 1 个人 1 个金币。

数据范围 30% 的测试数据，n≤1000 100%的测试数据，n≤1000000≥0 保证 ai 在 int 范围内， ai的总和在 long long 范围内。