序列 sequence

题目背景

原题 CF13C 数据加强版

题目描述

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

输入输出格式

输入格式

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

输出格式

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

输入输出样例

输入样例 #1

5
3 2 -1 2 11

输出样例 #1

输入样例 #2

5
2 1 1 1 1

输出样例 #2

说明

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