经历了忙碌而充实的一天，小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