T9625 10分求调（玄1关）

#include<bits/stdc++.h>
using namespace std;
int a[3000005],s[3000005],n,st[3000005],r[3000005],l[3000005];
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		s[i]=s[i-1]+a[i];
	}
	int p=-1;
	st[++p]=n;
	for(int i=n-1;i>=1;i--){
		while(p>-1&&a[st[p]]>=a[i]){
			p--;
		}
		if(p>-1)r[i]=st[p];
		else r[i]=0;
		st[++p]=i;
	}
	memset(st,0,sizeof(st));
	p=-1;
	st[++p]=n;
	for(int i=2;i<=n;i++){
		while(p>-1&&a[st[p]]>=a[i]){
			p--;
		}
		if(p>-1)l[i]=st[p];
		else l[i]=0;
		st[++p]=i;
	}
	int mx=0;
	for(int i=1;i<=n;i++){
		mx=max(mx,(s[r[i]-1]-s[l[i]])*a[i]);
	}
	cout<<mx;
	return 0;
}