【题目背景：】
原题cf13c 数据加强版（就是说原来能用DP做现在不行了QwQ）
【题目描述：】
给定一个序列，每次操作可以把某个数+1-1。要求把序列变成非降数列。而且要求修改后的数列只能出现修改前的数。
【输入格式：】
第一行输入一个n，表示有n( n \leq 5*10^5n≤5∗105 )个数字。第二行输入n个整数，整数的绝对值不超过 10^9109
【输出格式：】
输出一个数，表示最少的操作次数
【算法分析：】
切题背景：
chen_zhe大佬改编了这道题目之后吸引了slyz准高一全机房同学的注意
主要是一开始是道紫题想要通过以后强行把它变黑（雾
然后全机房的同学刚了一节课4597无果（中间它突然变成了黑题QwQ）
然后就被隔壁机房的学长学姐拯救了...
对于一个序列，可以看成高度不同的几根线
如：序列{3、 4、 1、 5}可以看做这样
----
----
---- ----
3 4 1 5
对于一个大数a和一个小数b，要做的就是在他们之间的任意位置找到一个基准，将大数向下挪到那个基准，小数向上挪到那个基准
移动的距离等价于a - b
由于是非降序列，将a向下移动的距离越多越可以使之后的数字更容易变成非降序列
所以这个基准应该是选择之前的最大数c，
当之前的最大数在[a, b]这个区间内，将a向下移到c并将b向上移到c的距离等价于将a向下移动到b的距离
所以就把a移到b就好了
而由于之前已经有一个c值，不把a,b移动到c也能保证之后答案的正确性
而当之后如果有许多个小数的时候，这么做也能保证之后答案的正确性，因为当前的c和当前b在这种情况里应该是同属于[之后的a, 之后的b]的区间内
当之前的最大数比b还要小的时候，b就变成了之前非降序列的一部分，a - b相当于将a向下移动到b
由于c是之前的最大数（也就是说现在的a > c），所以不存在c比a大的情况
然后开个大根堆瞎搞：
对于读进的一个数num，把它push到优先队列里去
如果这个num比之前的最大值maxn（就是堆顶元素）要小的话
ans += maxn - num
并把maxn弹出，再push进一个num(把maxn移动到了num的位置，这个操作正确性的证明见上面)
【代码：】
//序列sequence加强版
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std; int n;
long long ans;
priority_queue<int> q; inline int read() {
int x = , f = ; char ch = getchar();
while(ch < '' || ch > '') { if(ch == '-') f = -; ch = getchar(); }
while(ch >= '' && ch <= '')
x = (x << ) + (x << ) + ch - , ch = getchar();
return x * f;
} int main() {
n = read();
for(int i = ; i <= n; i++) {
int num = read();
q.push(num);
if(num < q.top()) {
ans += q.top() - num;
q.pop();
q.push(num);
}
}
printf("%lld\n", ans);
}