4591: 均分纸牌（第7题）
内存限制：256 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：0
解决：0
题目描述
经历了忙碌而充实的一天，小 X 正准备上床睡觉，这时他看到书桌上有一些纸牌被分成了 n 堆，n 堆纸牌排成一行，编号为 1,2,…,n，每堆纸牌有一定的张数(张数可能为 0，第i 堆的张数记为 ai)。见此情景，小 X 脑海中瞬间浮现出一道经典的编程题《均分纸牌》，他觉得如果在原题的基础上修改一些条件，将是一道非常好的压轴题。于是小Ｘ立刻拿出了纸和笔，认真地思考起来，首先他把全部纸牌的总张数改为不必为 n 的倍数，其次他将移动规则和最终目标也作了调整，移动规则改为可以在任意两堆之间移动任意张纸牌，目标是让张数最多的那堆纸牌的张数与张数最少的那堆纸牌的张数的差≤1。已知将第 i 堆的一张纸牌移动到第 j 堆的代价为|i-j|，|i-j|的值等于 i 与 j 的差值，如 i=3,j=5 时，|i-j|等于 2，反之 i=5,j=3时，|i-j|还是等于 2，也就是说无论你从第 3 堆向第 5 堆还是从第 5 堆向第 3 堆移动 1 张纸牌，所需的代价均为 2。现在小 X 想知道为了达成目标，他所消耗的代价最小为多少？
例如，当 n=5 时：
堆号 1 2 3 4 5
张数 5 9 2 12 9
移动的方法有多种， 其中的一种方案：
① 第 2 堆向第 1 堆移动 2 张，成为：7 7 2 12 9，消耗代价为 1*2=2② 第 4 堆向第 3 堆移动 4 张，成为：7 7 6 8 9，消耗代价为 1*4=4
③ 第 5 堆向第 3 堆移动 1 张，成为：7 7 7 8 8，消耗代价为 2*1=2 张数最多的堆有 8 张纸牌，张数最少的堆为 7 张纸牌，达成了任意两堆纸牌的张数差≤1 的目标，此时付出的代价为 2+4+2=8，可以证明找不到更小的可以达成目标的代价。
输入
第一行一个整数 n，表示纸牌的堆数。
第二行有 n 个用空格隔开的非负整数，表示每堆纸牌的张数。
输出
一行一个整数，表示所消耗的最小代价。
样例输入 复制
5
5 9 2 12 9样例输出 复制
8提示
数据规模与约定
对于20%的数据，n≤10，ai≤10
对于另外30的数据，保证纸牌的总数一定是n的倍数
对于100%的数据，n≤1000，ai≤10^6