均分物资

仓库里的补给比想象中多——六箱压缩食品，八瓶过滤水，还有一些医疗包。但你们现在有六个人：你、CC、Echo、老周、陈叔，还有 Echo 的投影虽然没有实体，但她的终端需要能源。

"每人该分多少？"CC把物资堆在地板上，金属手臂在搬重物时发出轻微的摩擦声。

"先算平均值。"你说，"总物资除以六，得到每人该得的数量。然后看每个人现在手里有多少，多了的给少了的。"

"环形坐。"老周忽然开口——这是他获救后说的第一句话，声音沙哑得像砂纸摩擦，"我们围成一圈，每次只能给相邻的人。这样最安全——Zero 的监控不会注意到小量的传递。"

你开始建模。六个人围成一个圈，每个人初始有 $a_i$ 个单位。目标是让所有人都有平均值。每次传递一个单位的代价是1。

"设 $x_i$ 表示第 $i$ 个人给第 $i+1$ 个人的数量。"你蹲下来，在地板上画了一个六边形，"第 $i$ 个人最终的数量是 $a_i - x_i + x_{i-1}$，等于平均值。所以 $x_i = x_{i-1} + a_i - avg$。"

CC在旁边看着："啥子意思？"

"意思是，所有人的传递量都取决于第一个人给第二个人的数量。只要确定了第一个人的给出量，后面所有人的传递量都被迫确定了。"

"那第一个人的给出量咋个定？"

"取中间值。"你说，"把所有可能的传递量算出来，取中间那个——这样总代价最小。"

你开始算。先算平均值，然后算每个人的差额，再算累积和。屏幕上跳出了六个传递量——有正有负，表示有的给出去，有的收进来。

"总代价是47。"你说。

"又是47。"CC说。

老周和陈叔对视了一眼。老周说："47号物资站。那里曾经是反抗军的补给点。"

"那现在呢？"CC问。

"现在……"老周的声音低了下去，"现在是Zero的陷阱。"

题目描述

$n$ 个人围成一圈，第 $i$ 个人有 $a_i$ 个单位的物资。每次只能给相邻的人传递一个单位，代价为1。求让所有人物资相等的最小总代价。

输入格式

$n$。然后 $n$ 个整数 $a_i$。

输出格式

最小总代价。

输入样例

3
1 2 3

输出样例

1

提示

• 设 $x_i$ 为第 $i$ 个人给第 $i+1$ 个人的数量。
• $x_i = x_{i-1} + a_i - avg$，其中 $avg$ 是平均值。
• 所有 $x_i$ 关于 $x_1$ 线性，取 $x_i$ 的中位数使总代价最小。

陈叔的芯片在终端上投射出一片密集的光点——G-30 矿区的守卫部署图。但这些光点不是单独给出的，而是用 $N$ 个等差序列压缩描述的：每个序列给出起始位置 $S$、结束位置 $E$、公差 $D$，代表守卫部署在 $S, S+D, S+2D, ..., E$ 这些位置上。

"这么多位置……"CC 盯着屏幕上滚动的数字，"咋个找那个奇点？"

"猜数字。"你说，"每次砍掉一半。"