rt，维护每个最小值和最大值能延伸的左右边界，然后枚举最大值，在最大值的左右边界里再暴力枚举最小值。

明显的 $O(n^2)$ 算法不仅通过了本题，而且轻轻松松最优解。。。。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn=500010;
const int mod=1000000000; 
inline int read(){
	int x=0;
	char c=getchar();
	for(;!(c>='0'&&c<='9');c=getchar());
	for(;c>='0'&&c<='9';c=getchar())
		x=(x<<1)+(x<<3)+c-'0';
	return x;
}
bool vis[maxn];
int L1[maxn],R1[maxn],L2[maxn],R2[maxn];	
int st[maxn],a[maxn],n,top;
int main(){
	n=read();
	for(int i=1;i<=n;i++) a[i]=read();
	for(int i=1;i<=n;i++){
		while(top&&a[st[top]]<=a[i])
			R1[st[top]]=i-1,top--;
		L1[i]=st[top]+1,st[++top]=i;
	}
	while(top) R1[st[top]]=n,top--;
	for(int i=1;i<=n;i++){
		while(top&&a[st[top]]>=a[i])
			R2[st[top]]=i-1,top--;
		L2[i]=st[top]+1,st[++top]=i;
	}
	while(top) R2[st[top]]=n,top--;
	ll tmp;
	int l,r,midl,midr,l_,r_,ans=0;
	for(int i=1;i<=n;i++){
		for(int j=L1[i];j<=R1[i];j++)
			if(!vis[j]){
				l=max(L1[i],L2[j]),r=min(R1[i],R2[j]);
				midl=min(i,j),midr=max(i,j);
				if(midl<l||midr>r) continue;
				l_=midr-l+1,r_=r-l+1;
				tmp=((l_+r_)*(r_-l_+1ll)/2)%mod;
				tmp=(tmp*(midl-l+1)%mod+(l_-r_-1)*(((midl-l)*(midl-l+1ll)/2)%mod)%mod+mod)%mod; 
				tmp=tmp*a[i]%mod*a[j]%mod;
				ans+=tmp,ans%=mod;
			}
		for(int j=L1[i];j<=R1[i];j++) vis[j]=0;
	}
	printf("%d\n",ans);
	return 0;
} 

两组数据：https://www.luogu.com.cn/problem/U210265

在附件里。