TouchStone
  Please Login
Login Sign Up
距离明年CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 Homepage  Problem Set  Examinations  Submissions  Discussions  Statistics
  • Home
  • Problem Set
  • P3951
  • Problem
  • P3951糖果传递
    Limits : Time Limit : - MS   Memory Limit : 165536 KB
    Judgment Tips : 1s
    Description

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

    Input Format

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

    Output Format

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

    Sample Input


    1
    2
    5
    4

    Sample Output

    4

    Hint

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