CF713C.Sonya and Problem Without a Legend

Sonya was unable to think of a story for this problem, so here comes the formal description.

You are given the array containing n positive integers. At one turn you can pick any element and increase or decrease it by 1. The goal is the make the array strictly increasing by making the minimum possible number of operations. You are allowed to change elements in any way, they can become negative or equal to 0.

索尼娅没能为本题构思出一个故事背景，因此这里给出其形式化描述。

给定一个包含 $n$ 个正整数的数组。每次操作中，你可以任选一个元素，将其加 $1$ 或减 $1$。目标是通过最少的操作次数，使该数组严格递增。你可以以任意方式修改元素，修改后的元素可以为负数或等于 $0$。

The first line of the input contains a single integer n (1 ≤ n ≤ 3000) — the length of the array.

Next line contains n integer a__i (1 ≤ a__i ≤ 109).

输入的第一行包含一个整数 $n$（$1 \leq n \leq 3000$）—— 表示数组的长度。

下一行包含 $n$ 个整数 $a_i$（$1 \leq a_i \leq 10^9$）。

Print the minimum number of operation required to make the array strictly increasing.

输出使数组严格递增所需的最少操作次数。

In the first sample, the array is going to look as follows:

2 3 5 6 7 9 11

|2 - 2| + |1 - 3| + |5 - 5| + |11 - 6| + |5 - 7| + |9 - 9| + |11 - 11| = 9

And for the second sample:

1 2 3 4 5

|5 - 1| + |4 - 2| + |3 - 3| + |2 - 4| + |1 - 5| = 12

在第一个样例中，数组将如下所示：

2 3 5 6 7 9 11

|2 - 2| + |1 - 3| + |5 - 5| + |11 - 6| + |5 - 7| + |9 - 9| + |11 - 11| = 9

而在第二个样例中：

1 2 3 4 5

|5 - 1| + |4 - 2| + |3 - 3| + |2 - 4| + |1 - 5| = 12