WA 0pts求调

#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read(){
	int f=1,x=0;
	char s=getchar();
	while(s<'0'||s>'9'){
		if(s=='-') f=-1;
		s=getchar();
	}
	while(s>='0'&&s<='9'){
		x=(x<<1)+(x<<3)+(s^48);
		s=getchar();
	}
	return x*f;
}
const int N=1e6+3;
int n,m,ans;
int a[N],uni[N];
vector<int>same[N];
int tr[N<<2];
void PushUp(int u){
	tr[u]=min(tr[u<<1],tr[u<<1|1]);
}
void Build(int u,int l,int r){
	if(l==r){
		tr[u]=a[l];
		return;
	}
	int mid=l+r>>1;
	Build(u<<1,l,mid);
	Build(u<<1|1,mid+1,r);
	PushUp(u);
}
void Update(int u,int l,int r,int x,int k){
	if(l==r){
		tr[u]=k;
		return;
	}
	int mid=l+r>>1;
	if(x<=mid) Update(u<<1,l,mid,x,k);
	else Update(u<<1|1,mid+1,r,x,k);
	PushUp(u);
}
int Query(int u,int l,int r,int x,int y){
	if(x<=l&&r<=y) return tr[u];
	int mid=l+r>>1,res=1e18;
	if(x<=mid) res=min(res,Query(u<<1,l,mid,x,y));
	if(y>mid) res=min(res,Query(u<<1|1,mid+1,r,x,y));
	return res;
}
int Query(int l,int r){
	if(l<=r) return Query(1,1,n,l,r);
	return 0;
}
int Change(int l,int r){
	return (l+r)*(r-l+1)/2%N;
}
int lmax[N],rmax[N];
bool vis[N];
set<int>sme;
void Solve(){
	n=read();
	for(int i=1;i<=n;i++){
		a[i]=read();
		uni[i]=a[i];
	}
	sort(uni+1,uni+n+1);
	m=unique(uni+1,uni+n+1)-uni-1;
	for(int i=1;i<=n;i++){
		a[i]=lower_bound(uni+1,uni+m+1,a[i])-uni;
		same[a[i]].push_back(i);
	}
	Build(1,1,n);
	int ltp=0,rtp=0;
	for(int i=1;i<=n;i++){
		lmax[i]=lmax[i-1];
		if(a[i]>lmax[i]){
			lmax[i]=a[i];
			ltp=i;
		}
	}
	for(int i=n;i>=1;i--){
		rmax[i]=rmax[i+1];
		if(a[i]>rmax[i]){
			rmax[i]=a[i];
			rtp=i;
		}
	}
	for(int i=1;i<=n;i++){
		int h=lmax[n];
		if(i<ltp) h=lmax[i];
		else if(i>rtp) h=rmax[i];
		same[h].push_back(i);
	}
	for(int i=1;i<m;i++){
		for(int j:same[i]){
			if(vis[j]){
				sme.erase(j);
				vis[j]=0;
			}else{
				sme.insert(j);
				vis[j]=1;
				Update(1,1,n,j,1e18);
			}
		}
		if(!sme.size()) continue;
		int lres=uni[i],rres=uni[i+1];
		if(sme.size()==1){
			int p=*sme.begin();
			ans=(ans+(Query(1,p-1)+Query(p+1,n))*(rres-lres)%N+Change(lres,rres-1))%N;
		}else{
			int x=*sme.begin(),y=*sme.rbegin(),sum=sme.size();
			ans=(ans+(min(Query(x+1,n),Query(1,y-1))
					+Query(1,x-1)+Query(y+1,n))*(rres-lres)%N
					+Change(lres+1,rres)*(2*sum-3)%N
					+sum*Change(lres,rres-1)%N)%N; 
		}
	}
	cout<<ans;
}
signed main(){
	int T=1;
	while(T--) Solve();
	return 0;
}