#P3293. [Cqoi2011]分金币

    ID: 2481 传统题 1000ms 512MiB 尝试: 1690 已通过: 908 难度: 6 上传者: 标签>难度分类提高排序与序列处理一维前缀和贪心中位数最小化绝对偏差和CF1900

[Cqoi2011]分金币

题目描述

有 nn 个人围坐在圆桌旁,每人最初持有一定数量的金币,金币总数是 nn 的倍数。每个人可以把金币转给左右相邻的人。最终,每个人持有的金币必须一样多。

一个金币每转交给相邻的人一次,就计入一次转手。求最少需要转手多少次。

输入格式

从标准输入读取。第一行是整数 nn。接下来 nn 行各有一个正整数,按逆时针的座位顺序给出每个人最初持有的金币数。

输出格式

向标准输出写入。输出一行一个整数,表示最少的转手次数。

样例 1

4
1
2
5
4
4

样例说明

按输入顺序将四人编号为 1,2,3,41,2,3,4。第 33 人给第 22 人两枚金币,四人的金币数变成 (1,4,3,4)(1,4,3,4)。随后第 22 人和第 44 人各给第 11 人一枚,四人各有三枚金币,共转手四次。

数据范围

3≤n≤1000003\le n\le100000,金币总数不超过 10910^9。