我的天，纯粹的大道至简。

我这里采取不同于题解的给出做法再出证明，尽力考虑怎么想到。

以单调不降为例说明。

从数学归纳的方面考虑，我们假定当前已经存在一种合法状态代表前 $i$ 个数，现在要加入第 $i+1$ 个数，想想还能保持合法需要什么条件，来反推合法状态需要的信息。

显然需要知道第 $i$ 位填什么，因为这限制了当前可填的范围。

设 $a_i$ 表示原数 $b_i$ 表示填的数。

分类讨论：

• 当 $a_{i+1}>=b_i$ 时，显然 $b_{i+1}=a_{i+1}$ 最优。

• 反之，发现考虑前 $i$ 个数不能确定最终序列，也就是说当前的 $b_i$ 是可调整的。

这时候 $b_i$ 调整为 $[a_{i+1},b_i]$ 都是最优的。（例如当前 $b$ 为 1,5,9;加入了一个4，9可以调整为8，变为1,5,8,8）。

我们期望调整的越小越好，因为这样后面的取值集合就会更大。

但是调整的下界就是当前存在的次大值。

说的很复杂但是代码又很简单的覆盖了这个概念。

#include<iostream>
#include<cstdio>
#include<queue>
#define int long long
using namespace std;
int n,a[500010];
priority_queue<int> q;
int res1,res2;
signed main(){
	cin >> n;
	for(int i=1;i<=n;i++){
		cin >> a[i];
		q.push(a[i]);
		if(a[i]<q.top()){
			res1+=q.top()-a[i];
			q.pop();q.push(a[i]);
		}
	}while(q.size()) q.pop();
	for(int i=n;i>=1;i--){
		q.push(a[i]);
		if(a[i]<q.top()){
			res2+=q.top()-a[i];
			q.pop();q.push(a[i]);
		}
	}
	cout << res1;
	return 0;
}