← 返回题目列表

Codeforces · 713/C

C. 索尼娅和没有传奇的问题

中文机器翻译题面 查看原题

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