题目背景

搬运自 http://czoj.com.cn/p/463。数据为民间数据。

题目描述

经历了忙碌而充实的一天，小 $\text{X}$ 正准备上床睡觉，这时他看到书桌上有一些纸牌被分成了 $n$ 堆，$n$ 堆纸牌排成一行，编号为 $1,2,\dots,n$，每堆纸牌有一定的张数（张数可能为 $0$，第 $i$ 堆的张数记为 $a_i$）。见此情景，小 $\text{X}$ 脑海中瞬间浮现出一道经典的编程题《均分纸牌》，他觉得如果在原题的基础上修改一些条件，将是一道非常好的压轴题。

于是小 $\text{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$。

现在小 $\text{X}$ 想知道为了达成目标，他所消耗的代价最小为多少？

输入格式

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

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

输出格式

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

5
5 9 2 12 9

8

提示

样例解释

• 堆号：$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$。

数据规模与约定

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

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

对于 $100\%$ 的数据，$1\le n≤1000$，$0\le a_i≤10^6$。