如题，空间是 $O(n)$ 的。

#include<bits/stdc++.h>
const int mod = 1e9;
using namespace std;
const int maxn = 5e5+14;
int ans,n;
int a[maxn];
int mx[maxn],mi[maxn];
struct Node{
	int mx,mi,len;
	Node(int MX=0,int MI=0,int LEN=0){
		mx=MX,mi=MI,len=LEN;
	}
};
vector<Node> vec[maxn]; 
int tr[maxn][2];//len mi*len mi
unordered_map<int,int> f;
int mp[maxn];
vector<int> S;
#define lowbit(x) (x&(-x))
inline void add(int u,int v,int type){
	v%=mod;
	while(u<maxn) tr[u][type]+=v,tr[u][type]%=mod,u+=lowbit(u);
}
inline int pre(int u,int type){
	int res=0;
	while(u>0) res+=tr[u][type],res%=mod,u-=lowbit(u);
	return res;
}
inline int ask(int l,int r,int type){
	return (pre(r,type)+mod-pre(l-1,type))%mod;
}
inline void solve(int l,int r){
	if(l==r){
		ans=(ans+1ll*mp[a[l]]*mp[a[l]])%mod;
		return ;
	}
	int mid=(l+r)>>1;
	solve(l,mid);
	solve(mid+1,r);
	mx[mid]=mi[mid]=a[mid];
	for(int i=mid-1;i>=l;i--) mx[i]=max(mx[i+1],a[i]),mi[i]=min(mi[i+1],a[i]);
	mx[mid+1]=mi[mid+1]=a[mid+1];
	for(int i=mid+2;i<=r;i++) mx[i]=max(mx[i-1],a[i]),mi[i]=min(mi[i-1],a[i]);
	//最大值在左边
	for(int i=mid;i>=l;i--){
		if(mx[mid+1]>mx[i]) continue;
		int lt=mid+1,rt=r+1;
		while(lt+1<rt){
			int MID=(lt+rt)>>1;
			if(mx[MID]<=mx[i]) lt=MID;
			else rt=MID;
		}
		vec[lt].push_back(Node(mp[mx[i]],mi[i],mid-i+1));
	}
	for(int i=mid+1;i<=r;i++){
		add(mi[i],1,0);
		add(mi[i],i-mid,1);
		//add(mi[i],1ll*mp[mi[i]]*(i-mid)%mod,2);
		//add(mi[i],mp[mi[i]],3);
		for(Node now:vec[i]){
			ans=(ans+((1ll*ask(now.mi,500005,1)*mp[now.mi]%mod)+(1ll*(1ll*mp[now.mi]*now.len%mod)*ask(now.mi,500005,0)%mod)%mod)*now.mx)%mod;
			//ans=(ans+1ll*((ask(1,now.mi-1,2)+1ll*(1ll*ask(1,now.mi-1,3)*now.len%mod))%mod)*now.mx)%mod;
		}
		//vec[i].clear();
	}
	for(int i=mid+1;i<=r;i++){
		add(mi[i],mod-1,0);
		add(mi[i],mod-(i-mid),1);
		//add(mi[i],mod-(1ll*mp[mi[i]]*(i-mid)%mod),2);
		//add(mi[i],mod-mp[mi[i]],3);
	}
	for(int i=mid+1;i<=r;i++){
		add(mi[i],1ll*mp[mi[i]]*(i-mid)%mod,0);
		add(mi[i],mp[mi[i]],1);
		for(Node now:vec[i]){
			//ans=(ans+((1ll*ask(now.mi,500005,1)*mp[now.mi]%mod)+(1ll*(1ll*mp[now.mi]*now.len%mod)*ask(now.mi,500005,0)%mod)%mod)*now.mx)%mod;
			ans=(ans+1ll*((ask(1,now.mi-1,0)+1ll*(1ll*ask(1,now.mi-1,1)*now.len%mod))%mod)*now.mx)%mod;
		}
		vec[i].clear();
	}
	for(int i=mid+1;i<=r;i++){
		//add(mi[i],mod-1,0);
		//add(mi[i],mod-(i-mid),1);
		add(mi[i],mod-(1ll*mp[mi[i]]*(i-mid)%mod),0);
		add(mi[i],mod-mp[mi[i]],1);
	}
	//最大值在右边
	for(int i=mid+1;i<=r;i++){
		int lt=l-1,rt=mid;
		if(mx[mid]>=mx[i]) continue;
		while(lt+1<rt){
			int MID=(lt+rt)>>1;
			if(mx[MID]<mx[i]) rt=MID;
			else lt=MID;
		}
		vec[rt].push_back(Node(mp[mx[i]],mi[i],i-mid));
	}
	for(int i=mid;i>=l;i--){
		add(mi[i],1,0);
		add(mi[i],mid-i+1,1);
		//add(mi[i],mp[mi[i]]*(mid-i+1)%mod,2);
		//add(mi[i],mp[mi[i]],3);
		for(Node now:vec[i]){
			ans=(ans+((1ll*ask(now.mi,500005,1)*mp[now.mi]%mod)+(1ll*(1ll*mp[now.mi]*now.len%mod)*ask(now.mi,500005,0)%mod)%mod)*now.mx)%mod;
			//ans=(ans+1ll*((ask(1,now.mi-1,2)+1ll*(1ll*ask(1,now.mi-1,3)*now.len%mod))%mod)*now.mx)%mod;
		}
		//vec[i].clear();
	}
	for(int i=mid;i>=l;i--){
		add(mi[i],mod-1,0);
		add(mi[i],mod-(mid-i+1),1);
		//add(mi[i],mod-(1ll*mp[mi[i]]*(mid-i+1)%mod),2);
		//add(mi[i],mod-mp[mi[i]],3);
	}
	for(int i=mid;i>=l;i--){
		//add(mi[i],1,0);
		//add(mi[i],mid-i+1,1);
		add(mi[i],mp[mi[i]]*(mid-i+1)%mod,0);
		add(mi[i],mp[mi[i]],1);
		for(Node now:vec[i]){
			//ans=(ans+((1ll*ask(now.mi,500005,1)*mp[now.mi]%mod)+(1ll*(1ll*mp[now.mi]*now.len%mod)*ask(now.mi,500005,0)%mod)%mod)*now.mx)%mod;
			ans=(ans+1ll*((ask(1,now.mi-1,0)+1ll*(1ll*ask(1,now.mi-1,1)*now.len%mod))%mod)*now.mx)%mod;
		}
		vec[i].clear();
	}
	for(int i=mid;i>=l;i--){
		//add(mi[i],mod-1,0);
		//add(mi[i],mod-(mid-i+1),1);
		add(mi[i],mod-(1ll*mp[mi[i]]*(mid-i+1)%mod),0);
		add(mi[i],mod-mp[mi[i]],1);
	}
}
int main(){
	//freopen("swamp.in","r",stdin);
	//freopen("swamp.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i],S.push_back(a[i]);
	sort(S.begin(),S.end());
	for(int x:S) if(f[x]==0) f[x]=f.size()+1,mp[f[x]]=x;
	for(int i=1;i<=n;i++) a[i]=f[a[i]];
	solve(1,n);
	cout<<ans<<'\n';
	return 0;
}