题目描述

有 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

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

1. 第 2 堆向第 1 堆移动 2 张，成为： 5 3 4 8

2. 第 4 堆向第 3 堆移动 3 张，成为： 5 3 7 5

3. 第 3 堆向第 2 堆移动 2 张，成为： 5 5 5 5

经过三次移动，每堆都成为 5 张。

输入格式

第一行一个整数 n 。

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

输出格式

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

样例

4
3 5 4 8

7