4029. HS的数

【题目背景】

HS不想说话...

【题目描述】

HS 给你长度为 $n$ 的数组 $a_i$，你可以用 $1$ 的费用使得一个 $a_i$ 加 $1$ 或者减 $1$。

HS 喜欢单调的数组，所以你需要将数组 $a$ 变成严格单调递增的数组，使得花费最小。

【输入格式】

第一行一个整数 $n$，表示数组 $a$ 的长度。

第二行 $n$ 个整数，第 $i$ 个整数表示 $a_i$。

【输出格式】

一个整数表示最小花费。

【样例输入1】

5
5 4 3 2 1

【样例输出1】

12

【样例输入2】

7
2 1 5 11 5 9 11

【样例输出2】

9

【样例说明】

第一个样例:

变为 $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$。

大洋里

【数据规模与约定】

对于 $50\%$ 的数据，有 $n\le 5000$。

对于 $100\%$ 的数据，有 $n\le 2\times 10^5，a_i \le 10^9$。

【来源】

codeforces.com/problemset/problem/713/C