Description

有 N 堆苹果，编号分别为 1，2，…, N,每堆有若干个苹果,苹果总数必为 N 的倍数。

可以在任一堆上取若于苹果，然后移动。

规则如下：

在编号为 1 堆上取的苹果，只能移到编号为 2 的堆上；

在编号为 N 的堆上取的苹果，只能移到编号为 N-1 的堆上；

其他堆上取的苹果，可以移到相邻左边或右边的堆上。

现在要求找出一种移动方法，用最少的移动次数使每堆上苹果数都一样多。

例如 N=4，4 堆苹果数分别为：9,8,17,6 移动3次可达到目的：

从第3堆 取4个放到第4堆得到 （9 8 13 10）

从第3堆 取3个放到第2堆得到 （9 11 10 10）

从第2堆取1个放到第1堆得到 （10 10 10 10）

Format

Input

N（N 堆苹果，1 <= N <= 100）

A1 A2 … An （N 堆苹果，每堆苹果初始数，1<= Ai <=10000）

Output

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

Samples

4
9 8 17 6

3