题目描述

圆桌上坐着 $n$ 个人，每人有一定数量的金币，金币总数能被 $n$ 整除。每个人可以给他左右相邻的人一些金币，最终使 得每个人的金币数目相等。

你的任务是求出被转手的金币数量的最小值。

输入格式

第一行为整数 $n$（$n \ge 3$）。

以下 $n$ 行每行一个正整数，按逆时针顺序给出每个人拥有的金币数。

输出格式

共一行，输出被转手金币数量的最小值。

4
1
2
5
4

4

提示

样例说明

设四个人编号为 $1,2,3,4$。第 $3$ 个人给第 $2$ 个人 $2$ 个金币（变成 $1,4,3,4$），第 $2$ 个人和第 $4$ 个人分别给第 $1$ 个人 $1$ 个金币。

数据范围

对于 $100\%$ 的数据，$3 \le n \le 10^5$，$总金币数 \le 10^9$。