序列 sequence

题目背景

原题 CF13C 数据加强版

题目描述

给定一个序列,每次操作可以把某个数 $+1$ 或 $-1$。要求把序列变成非降数列。而且要求修改后的数列只能出现修改前的数。

输入输出格式

输入格式


第一行,输入一个整数 $n$($n \leq 5 \times 10^5$),表示有 $n$ 个数字。 第二行输入 $n$ 个整数,整数的绝对值不超过 $10^9$。

输出格式


输出一个数,表示最少的操作次数。

输入输出样例

输入样例 #1

5
3 2 -1 2 11

输出样例 #1

4

输入样例 #2

5
2 1 1 1 1

输出样例 #2

1

说明

对于 $100 \%$ 的数据,$1 \le n \le 5 \times {10}^5$。