Background

出题人很懒，什么背景也没有留下。

Description

There is a row of N trees on the left side of the gate of Gaussia. They are arranged according to distance. The height of the first tree is a1 meters, the height of the second tree is a2 meters, the height of the third tree is a3 meters, ..., and the height of the n tree is an meters. In order to give the students a positive feeling, some students decided to trim the trees spontaneously, making the trees show an upward trend. Specifically, they want to trim and trim the trees so that the height b1,b2,b3,...,bn meters of the trimmed trees meet b1

高斯国城门的左侧有一排 n 棵树木。它们按照距离的远近排列，第 1 棵树的高度为 a1 米，第 2 棵树木的高度为 a2 米，第 3 棵树木的高度为 a3 米，……，第 n 棵树木的高度为 an米。
为了给同学们以积极向上的感觉，一些同学自发地决定对树木进行修剪，使得树木呈现上升的趋势。具体地说，他们希望对树木进行修剪和整理，使得修剪之后的树木高度 b1,b2,b3,...,bn 米且满足 b1<b2<b3<...<bn。
他们不仅可以对较高的枝条进行修剪使其高度减小，还可以通过枝条的加固使得树木的高度增加，而且可以使树木的高度减小和增加任意的高度，但一定得是整数（单位为米），而且最后树的高度必须大于零。然而，树木的整理只能在课间进行，因此他们没有太多的时间。对于一棵树，将其修剪使其高度减少 x 米需要花费 x 分钟的时间，将其整理加固使其高度增加 x 米也需要花费 x 分钟的时间。
参加这次活动的同学超过 n 个，因此所有树木可以同时得到修剪或整理。请你帮他们求出，最少要花费多少的时间可以修剪使得树木递增。注意：花费的总时间取决于最后完成修剪或整理的同学。

Format

Input

The first line of the input file contains an integer n, representing the number of trees. The second line of the input file contains n integers a1,a2,a3,...,an, representing the height of the first tree, the height of the second tree, the height of the third tree, ..., and the height of the nth tree.

输入文件的第一行包含 1 个整数 n，表示树木的个数。
输入文件的第二行包含 n 个整数 a1,a2,a3,...,an，表示第 1 棵树的高度、第 2 棵树的高度、第 3 棵树的高度、……、第 n 棵树的高度。

Output

The first line of the output file contains an integer that represents the shortest time that trees can be pruned so that they have an "upward trend."

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

Sample 1

Input

3
9 5 11

Output

3

Sample 2

Input

2
5 8

Output

0

Sample 3

Input

5
1 1 1 1 1

Output

4

Sample 4

Input

5
548 47 58 250 2012

Output

251

Sample description

在样例 1 中，可以把第 1 棵树花费 2 分钟降低 2 米，第 2 棵树花费 3 分钟增加 3 米，总共花费 3 分钟，最终的高度分别为 7m,8m,11m；
在样例 2 中，原来的树就已经呈现了上升的趋势，因此不需要进行修剪或整理，所需要的时间为 0 分钟；
在样例 3 中，可以把第 2 棵树花费 1 分钟增加 1 米，第 3 棵树花费 2 分钟增加 2 米，第 4 棵树花费 3 分钟增加 3 米，第 5 棵树花费 4 分钟增加 4 米，总共花费 4 分钟，最终的高度分别为 1m,2m,3m,4m,5m。

Limitation

对于 40% 的数据，n≤2；
对于 60% 的数据，n≤15；
对于 80% 的数据，ai≤3000；
对于 100% 的数据，n≤50,ai≤10^9。

Source

Amorphophallus Orz Group