均分纸牌

题目描述

有$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$)。

输入输出格式

输入格式


两行 第一行为:$N$($N$ 堆纸牌,$1 \le N \le 100$) 第二行为:$A_1,A_2, … ,A_n$ ($N$堆纸牌,每堆纸牌初始数,$1 \le A_i \le 10000$)

输出格式


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

输入输出样例

输入样例 #1

4
9 8 17 6

输出样例 #1

3