Building an Increasing Sequence

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.

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$)

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

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.