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.
## Input
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).
## Output
Print the minimum number of operation required to make the array strictly increasing.
[samples]
## Note
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
Sonya 无法为这个问题构思一个故事，因此以下是正式描述。
给定一个包含 #cf_span[n] 个正整数的数组。每次操作，你可以选择任意一个元素并将其增加或减少 #cf_span[1]。目标是通过最少的操作次数，使数组严格递增。你可以以任意方式修改元素，它们可以变为负数或等于 #cf_span[0]。
输入的第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 3000]) —— 数组的长度。
第二行包含 #cf_span[n] 个整数 #cf_span[ai] (#cf_span[1 ≤ ai ≤ 10^9])。
请输出使数组严格递增所需的最少操作次数。
在第一个样例中，数组将变为如下形式：
#cf_span[2] #cf_span[3] #cf_span[5] #cf_span[6] #cf_span[7] #cf_span[9] #cf_span[11]
#cf_span[|2 - 2| + |1 - 3| + |5 - 5| + |11 - 6| + |5 - 7| + |9 - 9| + |11 - 11| = 9]
对于第二个样例：
#cf_span[1] #cf_span[2] #cf_span[3] #cf_span[4] #cf_span[5]
#cf_span[|5 - 1| + |4 - 2| + |3 - 3| + |2 - 4| + |1 - 5| = 12]
## Input
输入的第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 3000]) —— 数组的长度。第二行包含 #cf_span[n] 个整数 #cf_span[ai] (#cf_span[1 ≤ ai ≤ 10^9])。
## Output
请输出使数组严格递增所需的最少操作次数。
[samples]
## Note
在第一个样例中，数组将变为如下形式：
#cf_span[2] #cf_span[3] #cf_span[5] #cf_span[6] #cf_span[7] #cf_span[9] #cf_span[11]
#cf_span[|2 - 2| + |1 - 3| + |5 - 5| + |11 - 6| + |5 - 7| + |9 - 9| + |11 - 11| = 9]
对于第二个样例：
#cf_span[1] #cf_span[2] #cf_span[3] #cf_span[4] #cf_span[5]
#cf_span[|5 - 1| + |4 - 2| + |3 - 3| + |2 - 4| + |1 - 5| = 12]
Let $ a = [a_1, a_2, \dots, a_n] $ be an array of $ n $ positive integers.
We seek a strictly increasing sequence $ b = [b_1, b_2, \dots, b_n] $ such that $ b_1 < b_2 < \dots < b_n $, and the total cost $ \sum_{i=1}^n |a_i - b_i| $ is minimized.
We are allowed to choose any real numbers $ b_i \in \mathbb{R} $, but since the cost function is piecewise linear and the optimal $ b_i $ will always coincide with some $ a_j $ (by properties of $ L_1 $-optimization and convexity), we may restrict $ b_i $ to lie in the set of values that appear in $ a $, or more generally, we may consider all integers (as operations are in integer steps).
However, a well-known transformation for this problem is to define:
$$
c_i = a_i - i
$$
Then the condition $ b_1 < b_2 < \dots < b_n $ becomes:
$$
b_i \geq b_{i-1} + 1 \quad \Rightarrow \quad b_i - i \geq b_{i-1} - (i-1)
$$
So defining $ d_i = b_i - i $, we require $ d_1 \leq d_2 \leq \dots \leq d_n $ (non-decreasing).
The cost becomes:
$$
\sum_{i=1}^n |a_i - b_i| = \sum_{i=1}^n |a_i - (d_i + i)| = \sum_{i=1}^n |(a_i - i) - d_i| = \sum_{i=1}^n |c_i - d_i|
$$
Thus, the problem reduces to:
Given array $ c = [c_1, c_2, \dots, c_n] $ where $ c_i = a_i - i $,
find a non-decreasing sequence $ d = [d_1, d_2, \dots, d_n] $ minimizing $ \sum_{i=1}^n |c_i - d_i| $.
This is the classic **"minimum cost to make array non-decreasing"** under $ L_1 $ norm, solvable via dynamic programming or the median trick (using the fact that the optimal $ d_i $ is a median of a certain set).
The minimal number of operations is:
$$
\min_{\substack{d_1 \leq d_2 \leq \dots \leq d_n \\ d_i \in \mathbb{R}}} \sum_{i=1}^n |c_i - d_i|
$$
where $ c_i = a_i - i $.
This value can be computed in $ O(n^2) $ using DP or in $ O(n \log n) $ using a heap-based method (e.g., using the "median maintenance" approach).
**Final formal statement:**
Let $ c_i = a_i - i $ for $ i = 1, 2, \dots, n $.
Find the minimum value of $ \sum_{i=1}^n |c_i - d_i| $ over all non-decreasing sequences $ d_1 \leq d_2 \leq \dots \leq d_n $, $ d_i \in \mathbb{R} $.
The answer is this minimum value.