#include<bits/stdc++.h>
using namespace std;
#define int __int128
#define lowbit(x) x&-x
#define maxx(a,b) a>b?a:b
const int N=1000010,MOD=9712176;
int n,a[N],tmp[N],tot,ans,tree1[N],tree2[N],f1[N],f2[N],dp1[N],dp2[N];
struct node{
	int l,r,cnt;
}mnlen[N],mxlen[N];
stack<int>stk;
void pre_work(){
	for(int i=1;i<=n;i++){
		tot=0;
		while(stk.size() && a[stk.top()]>a[i]){
			mnlen[stk.top()].r+=tot;
			tot+=(1+tmp[stk.top()]);
			stk.pop();
		}
		tmp[i]=tot;
		mnlen[i].l+=tmp[i];
		stk.push(i);
	}
	tot=0;
	while(stk.size()){
		mnlen[stk.top()].r+=tot;
		tot+=(1+tmp[stk.top()]);
		stk.pop();	
	}
	for(int i=1;i<=n;i++){
		tot=0;
		while(stk.size() && a[stk.top()]<a[i]){
			mxlen[stk.top()].r+=tot;
			tot+=(1+tmp[stk.top()]);
			stk.pop();
		}
		tmp[i]=tot;
		mxlen[i].l+=tmp[i];
		stk.push(i);
	}
	tot=0;
	while(stk.size()){
		mxlen[stk.top()].r+=tot;
		tot+=(1+tmp[stk.top()]);
		stk.pop();	
	}
	for(int i=1;i<=n;i++){
		mnlen[i].l=maxx(mnlen[i].l,1);
		mnlen[i].r=maxx(mnlen[i].r,1);
		mnlen[i].cnt=mnlen[i].l*mnlen[i].r;
		mxlen[i].l=maxx(mxlen[i].l,1);
		mxlen[i].r=maxx(mxlen[i].r,1);
		mxlen[i].cnt=mxlen[i].l*mxlen[i].r;
	}
}
void add1(int x,int sum){
	while(x<=n) tree1[x]=tree1[x]+sum,x+=lowbit(x);
}
void add2(int x,int sum){
	while(x<=n) tree2[x]=tree2[x]+sum,x+=lowbit(x);
}
int query1(int x){
	int sum=0;
	while(x) sum=sum+tree1[x],x-=lowbit(x);
	return sum;
}
int query2(int x){
	int sum=0;
	while(x) sum=sum+tree2[x],x-=lowbit(x);
	return sum;
}
signed main(){
	scanf("%lu",&n);
	for(int i=1;i<=n;i++){
		mnlen[i].l=mnlen[i].r=mxlen[i].l=mxlen[i].r=1;
		scanf("%lu",&a[i]);
	}
	pre_work();
	for(int i=1;i<=n;i++){
		f1[i]=query1(a[i]-1);
		dp1[i]=query2(a[i]-1);
		add1(a[i],a[i]*mxlen[i].cnt);
		add2(a[i],mxlen[i].cnt);
	}
	for(int i=1;i<=n;i++){
		tree1[i]=tree2[i]=0;
	}
	for(int i=n;i>=1;i--){
		f2[i]=query1(a[i]-1);
		dp2[i]=query2(a[i]-1);
		add1(a[i],a[i]*mxlen[i].cnt);
		add2(a[i],mxlen[i].cnt);
	}
	for(int i=1;i<=n;i++){
		ans=(ans+(mnlen[i].cnt*((f1[i]*f2[i])%MOD))%MOD)%MOD;
		ans=(ans+(((a[i]*a[i]*mnlen[i].cnt)%MOD)*((dp1[i]*dp2[i])%MOD)%MOD))%MOD;
		ans=(ans-((a[i]*mnlen[i].cnt)%MOD*(f1[i]*dp2[i])%MOD)%MOD+MOD)%MOD;
		ans=(ans-((a[i]*mnlen[i].cnt)%MOD*(f2[i]*dp1[i])%MOD)%MOD+MOD)%MOD;
	}
	printf("%lu",ans);
	return 0;
}