题目

#include<bits/stdc++.h>
using namespace std;
int a[1000010],l[1000010],r[1000010],l2[1000010],r2[1000010],anst,anss[1000010],manss,lsh[1000010],rsh[1000010],manst;
int main() {
	ios::sync_with_stdio(0);
	cin.tie(NULL);
	cout.tie(NULL);
	int t,n;
	cin>>t;
	while(t--) {
		manst=0,anst=0,manss=0;
		cin>>n;
		for(int i=0; i<n; i++)cin>>a[i];
		l[1]=a[0];lsh[1]=(a[0]>a[1])?0:n+1,l2[1]=0;
		for(int i=1; i<n-1; i++) {
			if(l2[i]>a[i])l2[i+1]=l2[i],l[i+1]=l[i],lsh[i+1]=lsh[i];
			else if(l[i]>a[i])l2[i+1]=a[i],l[i+1]=l[i],lsh[i+1]=lsh[i];
			else l2[i+1]=l[i],l[i+1]=a[i],lsh[i+1]=i;
		}
		r[n-2]=a[n-1];rsh[n-2]=(a[n-1]>a[n-2])?n-1:n+1,r2[n-2]=0;
		for(int i=n-2; i>0; i--) {
			if(r2[i]>a[i])r2[i-1]=r2[i],r[i-1]=r[i],rsh[i-1]=rsh[i];
			else if(r[i]>a[i])r2[i-1]=a[i],r[i-1]=r[i],rsh[i-1]=rsh[i];
			else r2[i-1]=r[i],r[i-1]=a[i],rsh[i-1]=i;
		}
		for(int i=0; i<n; i++) {
			if(a[i]<l[i]&&a[i]<r[i]) {
				anst+=min(l[i],r[i])-a[i];
				manst=max(manst,min(l[i],r[i])-a[i]);
				if(a[lsh[i]]==l[i]&&l2[i]<a[lsh[i]])anss[lsh[i]]+=(l2[i]<a[i])?min(l[i],r[i])-a[i]:min(l[i],r[i])-min(l2[i],r[i]);
				if(a[rsh[i]]==r[i]&&r2[i]<a[rsh[i]])anss[rsh[i]]+=(r2[i]<a[i])?min(l[i],r[i])-a[i]:min(l[i],r[i])-min(l[i],r2[i]);
			}
			cout<<i<<" "<<r[i]<<" "<<r2[i]<<" "<<rsh[i]<<" "<<l[i]<<" "<<l2[i]<<" "<<lsh[i]<<endl;
		}
		for(int i=0; i<n; i++) {
			manss=max(anss[i],manss);
			anss[i]=0;
			a[i]=0;
			l[i]=0;
			l2[i]=0;
			lsh[i]=0;
			r[i]=0;
			r2[i]=0;
			rsh[i]=0;
		}
		manss=anst-manss;
		cout<<min(anst-manst,manss)<<endl;
	}
  /*思路：首先找到左边最大和第二大的数，记录最大数的坐标，
  然后找到右边最大和最大的数，记录最大数的坐标，
  接着统计积水数量，找到拿来填最少有几个积水，拿来挖最少有几个积水，
  最后输出*/
}