Problem 2F. Change the list

Description

给定一个包含\(n\)个正整数的数组。在一个回合中你可以选择任何元素并增加或减少 1 。目标是通过尽可能少的操作使数组严格增加。您可以以任何方式更改元素，可以变为负值或等于 0 。

Input Format

输入的第一行包含一个整数 n ( 1 ≤ *n* ≤ 3000 ) — 数组长度。

Output Format

下一行包含 \(n\) 整数 \(a_i\) ( 1 ≤ \(a_i\) ≤ \(10^9\) )。

Test Case 1

input1

7
2 1 5 11 5 9 11

output1

9

Test Case 2

input2

5
5 4 3 2 1

output2

12

Note

对于样例1，数组 2 3 5 6 7 9 11 可以为 |2 - 2| + |1 - 3| + |5 - 5| + |11 - 6| + |5 - 7| + |9 - 9| + |11 - 11| = 9 。