Building an Increasing Sequence

Time limit2sMemory limit512 MB

Summary

Find a strictly increasing integer sequence B minimizing the total absolute difference from a given sequence A.

Level: Hard8 of 10
Topics: Greedy, Math
Solved: No attempts yet

Problem

An integer sequence $A_1, A_2, \dots, A_N$ is given.

Among all integer sequences $B$ that satisfy $B_1 < B_2 < \dots < B_N$ , take one that makes $|B_1 - A_1| + |B_2 - A_2| + \dots + |B_N - A_N|$ as small as possible and print that minimum value.

The sequences $A$ and $B$ consist of integers only, and every element of $B$ has to lie inside the range of a 32-bit integer type.

Input

The first line contains $N$ . ( $1 \le N \le 10^6$ )

The second line contains the elements of $A$ in order, $A_1, A_2, \dots, A_N$ . ( $0 \le A_i \le 2 \times 10^9$ )

Output

Print the smallest possible value of $|B_1 - A_1| + |B_2 - A_2| + \dots + |B_N - A_N|$ on one line.

Hint

For $A = (9, 4, 8, 20, 14, 15, 18)$ , the sequence $B = (6, 7, 8, 13, 14, 15, 18)$ minimizes the sum, and that minimum is 13.

Examples5

Example 1
Input
```
7
9 4 8 20 14 15 18
```
Expected output
```
13
```
Example 2
Input
```
1
0
```
Expected output
```
0
```
Example 3
Input
```
2
5 5
```
Expected output
```
1
```
Example 4
Input
```
5
1 2 3 4 5
```
Expected output
```
0
```
Example 5
Input
```
5
0 0 0 0 0
```
Expected output
```
6
```