#10180. 移动次数最少

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

题目描述

有n堆糖果(2≤n≤200),排成一行,编号分别为1,2,…n。

已知每堆糖果有一定的颗数,且颗数之和均为n的倍数。移动各堆中的任意颗糖果,使每堆的数量达到相同,且移动次数最少。

移动规则:

每次可以移动任意的糖果颗数,第1堆可以移向第2堆,第2堆可以移向第1堆或第3堆, ......, 第n 堆只可以移向第n -1堆。

例如,当n=4时:

堆号: 1 2 3 4

颗数: 9 8 17 6

移动的方法有许多种, 其中的一种方案:

① 第3堆向第4堆移动4颗,成为:9 8 13 10

② 第3堆向第2堆移动3颗,成为:9 11 10 10

③ 第2堆向第1堆移动1颗,成为:10 10 10 10

经过三次移动,每堆都成为10颗。

输入格式

有两行。

第一行一个整数n。

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

输出格式

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

样例

样例输入

4
9 8 17 6

样例输出

3