P4597 Sequence

Original problem CF13C, stronger testdata version.

Given a sequence, in each operation you may add $+1$ or $-1$ to any number. Make the sequence non-decreasing.

The first line contains an integer $n$ ($n \le 5 \times 10^5$), the number of elements. The second line contains $n$ integers; the absolute value of each integer does not exceed $10^9$.

Output a single number: the minimal number of operations.

For $100\%$ of the testdata, $1 \le n \le 5 \times 10^5$. Translated by ChatGPT 5