问题描述

详见教材p136问题描述： 有N堆纸牌，编号分别为1,2,...,N。每堆上有若干张，但纸牌总数必为N的倍数。可以在任一堆上取若张纸牌，然后移动。 移牌规则为：在编号为1堆上取的纸牌，只能移动到编号为2的堆上；在编号为N的堆上取的纸牌，只能移到编号为N-1的堆上；其他堆上取的纸牌，可以移到相邻左边或右边的堆上。 现在要求找出一种移动方法，用最少的移动次数使每堆上纸牌数都一样多。 例如N=4， 4堆纸牌分别为：①9 ②8 ③17 ④6 移动3次可达到目的： 从③取4张放到④（9 8 13 10）-> 从③取3张放到②（9 11 10 10） -> 从②取1张牌放到①（10 10 10 10）

格式

输入

第1行为一个整数$N$，表示N堆纸牌$(1 \le n \le 100)$; 第2行为$N$个整数，表示每堆纸牌初始数$Ai(l<Ai \le 10000)$。

输出

所有堆均达到相等时的最少移动次数。

样例

4
9 8 17 6

3

限制

1s, 64MB.