← 返回题目列表

AtCoder · awc0100_n

N. 股价调整

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

分数: 533 分

问题陈述

高桥正在分析某只股票的股价数据 N 天。当日股价 i is H_i 日元。

Takahashi 希望将这些股价数据纠正为“每天严格增加”的理想数据集,以便包含在报告中。具体来说,他想要修正后的股价 H'_1, H'_2, \ldots, H'_N 满足 H'_1 < H'_2 < \cdots < H'_N.

通过单独更改每天的股价来进行修正。当日股价变动时 i 来自 H_i to H'_i,成本为 |H_i - H'_i|。高桥希望最大限度地减少全天变更的总成本, \sum_{i=1}^{N} |H_i - H'_i|.

然而,修正后的股价 每一天的 H'_i 必须是整数。

修正股票价格时求出最小总成本,使它们在所有日子里严格单调递增。

约束

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq H_i \leq 10^9
  • 所有输入均为整数。

输入

N
H_1 H_2 \cdots H_N
  • 第一行包含一个整数 N 代表天数。
  • 第二行包含 N 整数 H_1, H_2, \ldots, H_N 代表每天的股价,以空格分隔。

输出

在一行中打印最小总成本。


示例输入 1

5
5 3 2 4 5

示例输出 1

6

示例输入 2

7
3 3 3 3 3 3 3

示例输出 2

12

示例输入 3

10
10 1 12 3 14 5 16 7 18 9

示例输出 3

50