调不过力:(

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mo = 1e9;
const int N = 5e5 + 1145;
int n;
ll ans,a[N],qzh[N];
ll qzmx[N],qzmn[N],qzhmx[N],qzhmn[N],qzsum[N],qzhsum[N];

void solve(int l,int r){
	if(r==l) {
		(ans+=a[l]*a[l]%mo)%=mo;
		return ; 
	}
	int mid=l+r>>1;
	solve(l,mid),solve(mid+1,r);
	ll mn=a[mid+1],mx=a[mid+1];
	for(int i=mid+1;i<=r;i++) {
		mx=max(mx,a[i]),mn=min(mn,a[i]);
		(qzmx[i]=mx+qzmx[i-1])%=mo,(qzmn[i]=mn+qzmn[i-1])%=mo;
		(qzhmx[i]=mx*(i-mid)%mo+qzhmx[i-1])%=mo,(qzhmn[i]=mn*(i-mid)%mo+qzhmn[i-1])%=mo;
		(qzsum[i]=mx*mn%mo+qzsum[i-1])%=mo,(qzhsum[i]=mx*mn%mo*(i-mid)%mo+qzhsum[i-1])%=mo;
	}
	mx=a[mid],mn=a[mid];
	int mnid=mid,mxid=mid;
	for(int i=mid;i>=l;i--){
		mx=max(mx,a[i]),mn=min(mn,a[i]);
		while(a[mnid+1]>mn&&mnid<r) mnid++; 
		while(a[mxid+1]<mx&&mxid<r) mxid++;
		int s1=min(mnid,mxid),s2=max(mnid,mxid);
		if(s1>mid) (ans+=mx*mn%mo*((mid+1-i+1+s1-i+1)*(s1-(mid+1)+1)/2%mo)%mo)%=mo;//(qzh[s1-i+1]-qzh[mid-i]+mo)%mo)%=mo;//懒得写式子 
		if(mnid>s1) (ans+=mn*(((mid-i+1)*(qzmx[s2]-qzmx[s1])%mo+qzhmx[s2]-qzhmx[s1]+mo)%mo))%=mo;//从mxid开始有比mx更大的数 
		if(mxid>s1) (ans+=mx*(((mid-i+1)*(qzmn[s2]-qzmn[s1])%mo+qzhmn[s2]-qzhmn[s1]+mo)%mo))%=mo;
		(ans+=(qzhsum[r]-qzhsum[s2]+mo)%mo+(mid-i+1)*(qzsum[r]-qzsum[s2]+mo)%mo)%=mo;
		
	}
	for(int i=mid+1;i<=r;i++) {
		qzmx[i]=0,qzmn[i]=0;
		qzhmx[i]=0,qzhmn[i]=0;
		qzsum[i]=0,qzhsum[i]=0;
	}
}

int main()
{
	cin>>n;
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	solve(1,n);
	cout<<ans;
	return 0;
}