题目描述

有 n 堆糖果( 2 ≤ n ≤ 200 )，排成一行，编号分别为 1 , 2 , ... , n 。已知每堆糖果有一定的颗数，且颗数之和均为 n 的倍数。移动各堆中的任意颗糖果，使每堆的数量达到相同，且移动次数最少。

移动规则：

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

例如，当 n=4 时：

移动的方法有许多种， 其中的一种方案：

1. 第 3 堆向第 4 堆移动 4 颗，成为： 9 8 13 10

2. 第 3 堆向第 2 堆移动 3 颗，成为： 9 11 10 10

3. 第 2 堆向第 1 堆移动 1 颗，成为： 10 10 10 10

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

输入格式

两行：

第一行一个整数 n ；

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

输出格式

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

样例

4                            
9 8 17 6

3