/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 533 点
問題文
高橋君は、ある銘柄の N 日間の株価データを分析しています。 i 日目の株価は H_i 円です。
高橋君は、レポートに掲載するため、この株価データを「毎日厳密に上昇している」理想的なデータに補正したいと考えています。すなわち、補正後の株価 H'_1, H'_2, \ldots, H'_N が H'_1 < H'_2 < \cdots < H'_N を満たすようにしたいです。
補正は各日の株価を個別に変更することで行います。 i 日目の株価を H_i から 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
- 1 行目には、日数を表す整数 N が与えられる。
- 2 行目には、各日の株価を表す N 個の整数 H_1, H_2, \ldots, H_N がスペース区切りで与えられる。
出力
コストの合計の最小値を 1 行で出力せよ。
入力例 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
Score : 533 pts
Problem Statement
Takahashi is analyzing stock price data for a certain stock over N days. The stock price on day i is H_i yen.
Takahashi wants to correct this stock price data into an ideal dataset that is "strictly increasing every day" for inclusion in a report. Specifically, he wants the corrected stock prices H'_1, H'_2, \ldots, H'_N to satisfy H'_1 < H'_2 < \cdots < H'_N.
The correction is performed by individually changing the stock price of each day. When changing the stock price on day i from H_i to H'_i, the cost is |H_i - H'_i|. Takahashi wants to minimize the total cost of changes across all days, \sum_{i=1}^{N} |H_i - H'_i|.
However, the corrected stock price H'_i for each day must be an integer.
Find the minimum total cost when correcting the stock prices so that they are strictly monotonically increasing across all days.
Constraints
- 1 \leq N \leq 2 \times 10^5
- 1 \leq H_i \leq 10^9
- All inputs are integers.
Input
N H_1 H_2 \cdots H_N
- The first line contains an integer N representing the number of days.
- The second line contains N integers H_1, H_2, \ldots, H_N representing the stock price on each day, separated by spaces.
Output
Print the minimum total cost in a single line.
Sample Input 1
5 5 3 2 4 5
Sample Output 1
6
Sample Input 2
7 3 3 3 3 3 3 3
Sample Output 2
12
Sample Input 3
10 10 1 12 3 14 5 16 7 18 9
Sample Output 3
50