题目描述

经历了忙碌而充实的一天，小 X 正准备上床睡觉，这时他看到书桌上有一些纸牌被分成了 $n$ 堆，$n$ 堆纸牌排成一行，编号为 $1,2,…,n$，每堆纸牌有一定的张数（张数可能为0，第 $i$ 堆的张数记为 $a_i$）。见此情景，小 X 脑海中瞬间浮现出一道经典的编程题《均分纸牌》，他觉得如果在原题的基础上修改一些条件，将是一道非常好的压轴题。于是小Ｘ立刻拿出了纸和笔，认真地思考起来，首先他把全部纸牌的总张数改为不必为 $n$ 的倍数，其次他将移动规则和最终目标也作了调整，移动规则改为可以在任意两堆之间移动任意张纸牌，目标是让张数最多的那堆纸牌的张数与张数最少的那堆纸牌的张数的差 $\leq 1$。已知将第 $i$ 堆的一张纸牌移动到第 $j$ 堆的代价为 $|i-j|$。现在小 X 想知道为了达成目标，他所消耗的代价最小为多少？

例如，当 $n=5$ 时

• 堆号：$\{1,2,3,4,5\}$
• 张数：$\{5,9,2,12,9\}$

移动的方法有多种， 其中的一种方案：

1. 第 2 堆向第 1 堆移动 2 张，成为：$\{7,7,2,12,9\}$，消耗代价为 $1 \times 2=2$
2. 第 4 堆向第 3 堆移动 4 张，成为：$\{7,7,6,8,9\}$，消耗代价为 $1 \times 4=4$
3. 第 5 堆向第 3 堆移动 1 张，成为：$\{7,7,7,8,8\}$，消耗代价为 $2 \times 1=2$

数最多的堆有 8 张纸牌，张数最少的堆为 7 张纸牌，达成了任意两堆纸牌的张数差$\leq 1$ 的目标，此时付出的代价为 $2+4+2=8$，可以证明找不到更小的可以达成目标的代价。

输入格式

第一行一个整数 $n$，表示纸牌的堆数

第二行有 $n$ 个用空格隔开的非负整数，表示每堆纸牌的张数。

输出格式

一行一个整数，表示所消耗的最小代价。

5
5 9 2 12 9

8

数据范围

对于 $20\%$ 的数据，$n\leq 10，a_i\leq 10$

对于另外 $30\%$ 的数据，保证纸牌的总数一定是$n$的倍数

对于 $100\%$ 的数据，$n\leq 1000$，$a_i\leq 10^6$