#7027. 【基础】均分纸牌 普及−

时间限制:1000 ms 内存限制:128 MiB 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

有n堆纸牌(2≤n≤200),排成一行,编号分别为1,2,…n。
已知每堆纸牌有一定的张数,且张数之和均为n的倍数。移动各堆中的任意张纸牌,使每堆的数量达到相同,且移动次数最少。
移动规则:
每次可以移动任意的张数,第1堆可以移向第2堆,第2堆可以移向第1堆或第3堆,。。。。。。 第n 堆只可以移向第n -1堆。
例如,当n=4时:

堆号      1     2     3     4 
张数 3 5 4 8

移动的方法有许多种, 其中的一种方案:
① 第2堆向第1堆移动2张,成为:5 3 4 8
② 第4堆向第3堆移动3张,成为:5 3 7 5
③ 第3堆向第2堆移动2张,成为:5 5 5 5
经过三次移动,每堆都成为5张。

输入格式

第一行一个整数n。第二行n个整数,用空格分隔。

输出格式

一个整数(表示最少移动次数)。

样例

样例输入1

4 
3 5 4 8

样例输出1

3