估计是全网最复杂题解。。。

给定数组上的操作：选定一个前缀或者后缀，将内部的所有数+1，花费是长度。现给出目标数组 \(a_i\)，求最少花费，能够让初始全为 0 的 \(b_i\) 满足 \(b_i\ge a_i\)。

反向考虑：将 \(a_i\) 进行减操作，使得每个数都小于等于 0。考虑差分，差分后将区间减转变为单点的加减，但是这样一来每个数都小于等于 0 的判定就变成了要判定前缀和是否都小于等于 0，这不太好处理。

考虑增加一个区间加操作，对 \([l,r]\) 的区间内的 \(a_i\) 加 1，花费为 0。可以想象为通过原本的操作把 \(a_i\) 操作至非正后，又把负数全部再加回 0。这样一来相当于通过增加一个“不优”的操作将终止条件从全部非正转化为了全部都要是 0，方便后续讨论。

看看现在问题是什么。给定一个数组 \(a_i\)，其中有正有负。操作1（前缀）：\(a_1-=1\)，\(a_{r+1}+=1\)，花费代价 \(r\)。操作2（后缀）：\(a_l-=1\)，花费代价 \(n-l+1\)。操作3（调整）：\(a_x+=1\)，\(a_y-=1\)，满足 \(x<y\)，花费为 0。通过这三个操作，将 \(a_i\) 全部变为 0，求最小代价。

几个观察：

首先，操作是满足交换律的，也就是说最优解中的操作序列打乱顺序后依然是最优解。

由于 \(a_i\) 中的数全部要变为 0，那么我们不会把正数变大，不会把负数变小，也不会对 0 做任何操作。

假设没有负数，最优方案很显然：对每个正数做操作2直到变小至0。但有了负数之后，这样做就不优了，这是因为负数能够在一定程度上优化正数变小的开销。举例说，如果有一个 “ ... -1 ... +1 ...”，我们可以通过操作3，不消耗任何代价使得后面的 +1 变为 0；如果有一个 " ... +1 ... -1 ..."，我们先通过对 -1 进行操作1，花费代价 r 将 -1 转移到 \(a_1\) 去，然后就转化成了上面的情况，再使用操作3即可。这相当于花费 r，使得前面的 +1 变为 0。具体的，假设说 +1 在位置 \(i\)，-1 在位置 \(j\)，如果 \(j<i\)，即 -1 在 +1 前面，我们可以让 +1 的原本的 \(n-i+1\) 的花费降低至 0；如果 \(j>i\)，可以把花费降低至 \(j-1\)。

有了上面的观察，我们可以进一步转化题目：先不考虑负数，只用操作2把所有正数变成 0 并计算花费，然后剩下一堆负数没有用，再考虑负数能够通过操作1、3最多挽回多少损失。一个 -1 通过操作3，可以退回右侧 +1 之前的操作2的开销；通过操作1+操作3，可以退回左侧 +1 之前的操作2的开销。

具体来说，假设说有一个 -1 在 \(j\) 的位置，它可以通过操作1和3去处理一个在 \(j\) 之前的 \(i\) 处的 +1，挽回 \(w(j)=n-i+1-(j-1)\) 的花费，也可以选择通过操作3去处理一个在 \(j\) 之后的 \(k\) 处的一个 +1，挽回 \(w(k)=n-k+1\) 的花费。这两个花费分别就是在左侧的 +1 和在右侧的 +1 的价值。

问题变成了每一个负数的抉择：分多少 -1 给左边，分多少 -1 给右边？

这里我们使用贪心策略，每一次选择当前能够挽回最多代价的一对 -1 和 +1。这样的最优配对有什么特征？

我们发现，不论最优配对的 +1 在哪里，其配对的 -1 一定是当前在最左边的那个 -1（操作1花费最小，且能对最多正数做操作3）。也就是说，越靠左的 -1 越厉害，而且最优配对的 -1 一定是最左边的 -1。

所以每一次最佳配对的 -1 都是确定的，只需要每次找到最优的 +1 ，也就是要找到使得 \(w(j)\) 最大的 j。

注意到：

1. 越靠左的 +1 消耗的操作2的代价越大，选择它能挽回的代价就越多。
2. 同在左侧的 +1 都需要 -1 做一次操作1，同在右侧的 +1 都不需要这个操作1。

综上，最优的 +1 一定是 -1 两侧的最左边的两个 +1 中的一个。比较一下选择最优的即可。

但上述讨论姑且只是在只考虑一步的情况下的最优解，如果允许先前已经配对好的 -1 重新决定配对，当前最优的 +1 可能会变化。也就是说，之前已经做出的局部最优抉择可能会在后面发现不是最优的，需要进行反悔。

情况1： "... +1 ... -1 ... +1 ... -1 ..."：先前考虑到 2 时，组成了配对 (2,1)，然后在考虑到 4 时，组成了配对 (4,3)，目前为止每一步配对都在当时是最优的。但现在我们知道，如果我们对于”在考虑 2 时做出的抉择“进行反悔：让 2 不再和 1 配对而是和 3 配对，然后失去配对的 1 由 4 接管，那么就可以省去一个操作1（省去一个 \(i_2-1\) 的代价）。即 (2,1)(4,3) 可以反悔成 (2,3)(4,1)。如何进行反悔？

考虑进行反悔后会发生什么。如果应用了这个反悔，我们发现：当前情况下选择将位于 3 的 +1 下降所能挽回的最多的价值其实不是 \(n-i_3+1-(i_4-1)\) 而是 \(n-i_3+1-(i_4-1)+(i_2-1)\)。所以，原先对处于当前 -1 的左边的 +1 做出的估价函数，可以再增加一项。

在当前考虑的 -1(i) 的左边的 +1(j)，如果它的左边还有一个最近的一个先前抉择好的配对 \((p,q)\)，满足 \(q<p<j<i\) 且 p 最大，那么通过配对 \((p,j)(i,q)\)，计算得新的价值函数 \(w'(j)=n-j+1-(i-1)+(p-1)\)。这个价值函数相比于先前的，能够多挽回 \(p-1\) 的价值。

通过允许反悔，优化了左侧 +1 的估价函数，反过来说，通过获取更新后的价值，也相当于自动完成了对先前抉择的反悔。

情况2：" +1 ... -1 -1 +1 ..."：位于 2 的 -1 在当时选择了右边最近的 +1，即与位于 4 的 +1 配对成 (2,4)，但显然全局最优解会选择将 3 与 4 配对。这是因为，如果配对 (3,4)，那么为了消去 1 所需要的操作1，可以由 2 而不是 3 来做，优化了操作 1 的花费。即 (2,4)(3,1) 可以反悔成 (2,1)(3,4)。如何进行反悔？

可以仿照情况一，对能够优化的 +1 的价值函数进行修改。

比如当前考虑到的 -1 位于 \(i\)，且存在一个配对 \((p,q)\) 满足 \(p<i<q\)，那么对于 \(j<p<i<q\) 的 \(j\)，通过配对 \((p,j)(i,q)\) 其价值优化为 \(w'(j)=n-j+1-(p-1)\)，相比于之前多挽回 \(i-p\) 的价值。但这个相比于情况一难处理得多。

实际上，我们可以通过直接避免这种情况的发生来避免反悔。注意到一段连续的 -1 中的每一个与右边最近的 +1 配对时价值相同，但是如果我们总是选择连续段中最右边的 -1 去跟右边的 +1 配对，就不会发生情况2。

故我们不再每次只考虑最左边的一个 -1，而是考虑最左边的连续的一段 -1（内部没有正数），那么左边的 +1 还是会与最左边的 -1 配对，而右边 +1 会与连续段的最右边的 -1 配对。

解决了上述的两种情况，我们可以做到：在综合考虑当前的抉择和过去所有抉择的反悔的情况下，每次都能找到最优的一步选择。这归功于我们找到了允许反悔的情况下的每一个 +1 的价值函数。这样每次选择价值函数最高的 +1 的贪心，最终就可以获得最优解。

这个问题实际上可以转化为费用流问题，上述贪心和反悔实际上是在模拟费用流的进退流过程，因此可以获得严谨的正确性证明。

因为实现相当复杂，所以这里给一下代码

const int N=1e6+3;
int a[N];
struct node{
	int c;
	queue<pair<int,int>>Q;
};
node T[N];
struct prq{
	int k,v;
	bool operator<(const prq &a)const{return v>a.v;}
};
void solve(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	ll ans=0;
	stack<int>S;
	priority_queue<prq>P;
	auto push=[&](int u,int t,int i){
		if(t==0)return;
		if(T[u].Q.empty()){
			P.push({u,i-u});
		}
		T[u].Q.push({t,i});
	};
	auto get=[&](int x){
		auto [k,v]=P.top();
		auto &q=T[k].Q;
		int &d=q.front().first;
		if(d>x){
			d-=x;
			return x;
		}
		q.pop();
		P.pop();
		if(q.size()){
			P.push({k,q.front().second-k});
		}
		return d;
	};
	int p=1;
	for(int i=n;i;i--){
		T[i].c=0;
		T[i].Q=queue<pair<int,int>>();
		a[i]-=a[i-1];
		if(a[i]>0)ans+=a[i]*(n-i+1ll);
	}
	S.push(1);
	T[1].c=-1;
	deque<int>D;
	for(int i=1;i<=n;i++){
		while(a[i]>0){
			int u=S.top(),tmp;
			if(u==1)tmp=a[i];
			else tmp=min(a[i],T[u].c);
			a[i]-=tmp;
			if(u!=1)T[u].c-=tmp;
			push(u,tmp,i);
			if(T[u].c==0)S.pop();
		}
		while(a[i]<0){
			while(D.size()&&D.front()!=i)D.pop_front();
			if(D.empty())D.push_back(i);
			p=max(p,i+1);
			while(p<=n&&a[p]<=0){
				if(a[p]<0)D.push_back(p);
				p++;
			}
			assert(P.size());
			int v1=n-i+1-P.top().v,v2=n-p+1;
			int j=D.back();
			if(p<=n&&v2>v1){
				int tmp=min(-a[j],a[p]);
				a[j]+=tmp;
				a[p]-=tmp;
				ans-=(ll)tmp*v2;
				if(a[j]==0)D.pop_back();
			}
			else if(v1>0){
				int tmp=get(-a[i]);
				a[i]+=tmp;
				ans-=(ll)tmp*v1;
				T[i].c+=tmp;
			}
			else break;
		}
		if(T[i].c)S.push(i);
	}
	cout<<ans<<endl;
}