Sonya 无法为这个问题想出一个故事,所以这里是正式的描述。
给定一个包含 n 个正整数的数组。在一轮中,您可以选择任何元素并将其增加或减少 1。目标是通过尽可能少的操作次数使数组严格增加。您可以以任何方式更改元素,它们可以变为负数或等于 0。
输入
输入的第一行包含一个整数 n (1 ≤ n ≤ 3000) — 数组的长度。
下一行包含 n 个整数 ai (1 ≤ ai ≤ 109)。
输出
打印使数组严格递增所需的最少操作数。
示例
输入 #1
7 2 1 5 11 5 9 11
输出 #1
9
输入 #2
5 5 4 3 2 1
输出 #2
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