容易發(fā)現(xiàn)相交的區(qū)間是不會(huì)產(chǎn)生貢獻(xiàn)的。于是不用考慮這個(gè)限制。

用單調(diào)棧可以求出以 \(a_i\) 為最小值和最大值的區(qū)間個(gè)數(shù) \(qmn_i\) 和 \(qmx_i\)。

從小到大枚舉第二個(gè)區(qū)間的最小值，記 \(p_i\) 表示 \(i\) 的位置，則對(duì)于 \(i\) 的答案即為：

簡(jiǎn)單推式子后得到：

\( qmn_{p_i}(\sum{qmx_j}\sum{qmx_k}i^2-\sum{qmx_ja_j}\sum{qmx_k}i-\sum{qmx_j}\sum{qmx_ka_k}i+\sum{qmx_ja_j}\sum{qmx_ka_k}) \)

于是開(kāi)兩棵樹(shù)狀數(shù)組維護(hù) \(qmx_j\) 和 \(qmx_ja_j\) 就好了。時(shí)間復(fù)雜度 \(O(n\log n)\)。

#include<bits/stdc++.h>
#define ll long long
#define il inline

using namespace std;
namespace asbt{
namespace cplx{bool begin;}
const int maxn=1e6+5,mod=9712176;
int n,a[maxn],p[maxn],zhan[maxn];
int lmn[maxn],rmn[maxn];
int lmx[maxn],rmx[maxn];
int qmn[maxn],qmx[maxn];
struct{
	int tr[maxn];
	il int lowbit(int x){
		return x&-x;
	}
	il void upd(int p,int v){
		for(;p<=n;p+=lowbit(p)){
			(tr[p]+=v)%=mod;
		}
	}
	il int query(int p){
		int res=0;
		for(;p;p-=lowbit(p)){
			(res+=tr[p])%=mod;
		}
		return res;
	}
	il int query(int l,int r){
		return (query(r)-query(l-1)+mod)%mod;
	}
}F1,F2;
namespace cplx{
	bool end;
	il double usdmem(){return (&begin-&end)/1048576.0;}
}
int main(){
	ios::sync_with_stdio(0),cin.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		p[a[i]]=i;
	}
	for(int i=1,top=0;i<=n;i++){
		while(top&&a[zhan[top]]>a[i]){
			top--;
		}
		lmn[i]=zhan[top];
		zhan[++top]=i;
	}
	for(int i=1,top=0;i<=n;i++){
		while(top&&a[zhan[top]]<a[i]){
			top--;
		}
		lmx[i]=zhan[top];
		zhan[++top]=i;
	}
	zhan[0]=n+1;
	for(int i=n,top=0;i;i--){
		while(top&&a[zhan[top]]>a[i]){
			top--;
		}
		rmn[i]=zhan[top];
		zhan[++top]=i;
	}
	for(int i=n,top=0;i;i--){
		while(top&&a[zhan[top]]<a[i]){
			top--;
		}
		rmx[i]=zhan[top];
		zhan[++top]=i;
	}
	for(int i=1;i<=n;i++){
		qmn[i]=(i-lmn[i])*1ll*(rmn[i]-i)%mod;
		qmx[i]=(i-lmx[i])*1ll*(rmx[i]-i)%mod;
	}
	int ans=0;
	for(int i=1,xj,xaj,xk,xak;i<=n;i++){
		xj=F1.query(1,p[i]-1);
		xaj=F2.query(1,p[i]-1);
		xk=F1.query(p[i]+1,n);
		xak=F2.query(p[i]+1,n);
		(ans+=qmn[p[i]]*1ll*(xj*1ll*xk%mod*i%mod*i%mod-xaj*1ll*xk%mod*i%mod-xj*1ll*xak%mod*i%mod+xaj*1ll*xak%mod)%mod)%=mod;
		(ans+=mod)%=mod;
		F1.upd(p[i],qmx[p[i]]);
		F2.upd(p[i],qmx[p[i]]*1ll*i%mod);
	}
	cout<<ans;
	return 0;
}
}
int main(){return asbt::main();}