题目描述

桌上一字排开 $N$ 叠卡片，从左到右编号 $1,2,\ldots,N$。每叠上有若干张卡片，且卡片总数恰好是 $N$ 的倍数。每次操作可以从某一叠上拿走任意张卡片，并放到相邻的一叠上：编号 $1$ 的叠只能往编号 $2$ 的叠放，编号 $N$ 的叠只能往编号 $N-1$ 的叠放，其余各叠可以放到左右任意一侧的相邻叠上。

请计算：最少需要多少次操作，才能让每叠上的卡片张数完全相同。

例如 $N=4$，各叠卡片数为 $9,8,17,6$ 时，操作 $3$ 次即可：

• 从第三叠取 $4$ 张放到第四叠，变为 $9,8,13,10$；
• 从第三叠取 $3$ 张放到第二叠，变为 $9,11,10,10$；
• 从第二叠取 $1$ 张放到第一叠，变为 $10,10,10,10$。

输入格式

第一行一个整数 $N$，表示卡片的叠数。
第二行共 $N$ 个整数 $A_1,A_2,\ldots,A_N$，依次表示每叠卡片初始时的张数。

输出格式

一行一个整数，表示让所有叠卡片数相等所需的最少操作次数。

样例

4
9 8 17 6

3

提示

对于 $100\%$ 的数据，$1 \le N \le 100$，$1 \le A_i \le 10000$。