Description

学校大门的左侧有一排 $n$ 棵树木。它们按照距离的远近排列，第 $1$ 棵树的高度为 $a_1$ 米，第 $2$ 棵树木的高度为 $a_2$ 米，第 $3$ 棵树木的高度为 $a_3$ 米，……，第 $n$ 棵树木的高度为 $a_n$ 米。

为了给同学们以积极向上的感觉，一些同学自发地决定对树木进行修剪，使得树木呈现上升的趋势。具体地说，他们希望对树木进行修剪和整理，使得修剪之后的树木高度 $b_1,b_2,b_3, \cdots ,b_n$ 米且满足 $b_1<b_2<b_3< \cdots <b_n$。

他们不仅可以对较高的枝条进行修剪使其高度减小，还可以通过枝条的加固使得树木的高度增加，而且可以使树木的高度减小和增加任意的高度，但一定得是整数（单位为米），而且最后树的高度必须大于零。然而，树木的整理只能在课间进行，因此他们没有太多的时间。对于一棵树，将其修剪使其高度减少 $x$ 米需要花费 $x$ 分钟的时间，将其整理加固使其高度增加 $x$ 米也需要花费 $x$ 分钟的时间。

参加这次活动的同学超过 $n$ 个，因此所有树木可以同时得到修剪或整理。请你帮他们求出，最少要花费多少的时间可以修剪使得树木递增。注意：花费的总时间取决于最后完成修剪或整理的同学。

Input Format

从文件 tree.in 中读取数据。

输入文件的第一行包含 $1$ 个整数 $n$ ，表示树木的个数。

输入文件的第二行包含 $n$ 个整数 $a_1,a_2,a_3,/cdots,a_n$，表示第 $1$ 棵树的高度、第 $2$ 棵树的高度、第 $3$ 棵树的高度、……、第 $n$ 棵树的高度。

Output Format

输出到文件 tree.out 中去。

输出文件的第一行包含 $1$ 个整数，表示能修剪使得树木具有“向上的趋势”的最短时间。

Sample

样例输入1

3
9 5 11

样例输出1

3

样例1解释

在样例 $1$ 中，可以把第 $1$ 棵树花费 $2$ 分钟降低 $2$ 米，第 $2$ 棵树花费 $3$ 分钟增加 $3$ 米，总共花费 $3$ 分钟，最终的高度分别为 $7m,8m,11m$；

样例输入2

2
5 8

样例输出2

0

样例2解释

在样例 $2$ 中，原来的树就已经呈现了上升的趋势，因此不需要进行修剪或整理，所需要的时间为 $0$ 分钟；

样例输入3

5
1 1 1 1 1

样例输出3

4

样例3解释

在样例 $3$ 中，可以把第 $2$ 棵树花费 $1$ 分钟增加 $1$ 米，第 $3$ 棵树花费 $2$ 分钟增加 $2$ 米，第 $4$ 棵树花费 $3$ 分钟增加 $3$ 米，第 $5$ 棵树花费 $4$ 分钟增加 $4$ 米，总共花费 $4$ 分钟，最终的高度分别为 $1m,2m,3m,4m,5m$。

样例输入4

5
548 47 58 250 2012

样例输出4

251

Hint

对于 $40\%$ 的数据，$n \le 2$；

对于 $60\%$ 的数据，$n \le 15$；

对于 $80\%$ 的数据，$a_i \le 3000$；

对于 $100\%$ 的数据，$n \le 50$ , $a_i \le 10^9$。