TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P3951
  • 题目
  • P3951糖果传递
    限制 : 时间限制 : - MS   空间限制 : 165536 KB
    评测说明 : 1s
    问题描述

    何老板准备了一堆糖果, 恰好n个同学可以分到数目一样多的糖果. 何老板要n个同学去拿糖果,
    然后围着圆桌坐好, 第1个同学的左边是第n个同学, 其他第i个同学左边是第i-1个小朋友. 大家坐好后, 何老板发现, 有些同学抢了很多的糖果, 有的同学只得到了一点点糖果, 甚至一颗也没有 ?,设第i个同学有ai颗糖果. 同学们可以选择将一些糖果给他左边的或者右边的同学, 通过”糖果传递”最后使得每个同学得到的糖果数是一样多的, 假设一颗糖果从一个同学传给另一个同学的代价是1, 问怎样传递使得所耗的总代价最小.

    输入格式

    第一行一个正整数n,表示同学的个数.
    接下来n行,每行一个整数ai,表示第i个同学得到的糖果的颗数.

    输出格式

    输出只有一个数, 表示最小代价.

    样例输入


    1
    2
    5
    4

    样例输出

    4

    提示

    数据范围 
    30%的测试数据, n<=1000.
    100%的测试数据, n<=200000.
    ai>=0, 保证ai在longint/int范围内, ai的总和在int64/long long范围内.