#include<bits/stdc++.h>
#define int long long
using namespace std;

const int NR = 5e5;
const int mod = 1e9;
const int inf = 9e18;

int n, a[NR + 5], lmin[NR + 5], lmax[NR + 5], rmin[NR + 5], rmax[NR + 5];
int s1[NR + 5], _s1[NR + 5], s2[NR + 5], _s2[NR + 5], s3[NR + 5], _s3[NR + 5];

int solve(int l, int r) {
	if(l == r) return a[l] * a[l];
	int mid = (l + r) / 2, res = 0;
	res = (res + solve(l, mid)) % mod;
	res += solve(mid + 1, r);
	lmin[mid + 1] = inf;
	lmax[mid + 1] = 0;
	for(int i = mid; i >= l; i--) {
		lmin[i] = min(lmin[i + 1], a[i]);
		lmax[i] = max(lmax[i + 1], a[i]);
	}
	rmin[mid] = inf;
	rmax[mid] = 0;
	for(int i = mid + 1; i <= r; i++) {
		rmin[i] = min(rmin[i - 1], a[i]);
		rmax[i] = max(rmax[i - 1], a[i]);
	}
	s1[l - 1] = _s1[l - 1] = 0;
	s2[l - 1] = _s2[l - 1] = 0;
	s3[l - 1] = _s3[l - 1] = 0;
	for(int i = l; i <= mid; i++) {
		s1[i] = (s1[i - 1] + lmin[i] % mod * lmax[i] % mod * (i - 1) % mod) % mod;
		_s1[i] = (_s1[i - 1] + lmin[i] % mod * lmax[i] % mod) % mod;
		s2[i] = (s2[i - 1] + lmin[i] % mod * (i - 1) % mod) % mod;
		_s2[i] = (_s2[i - 1] + lmin[i]) % mod;
		s3[i] = (s3[i - 1] + lmax[i] % mod * (i - 1) % mod) % mod;
		_s3[i] = (_s3[i - 1] + lmax[i]) % mod; 
	}
	int p1 = mid, p2 = mid;
	for(int j = mid + 1; j <= r; j++) {
		while((lmin[p2] > rmin[j] && lmax[p2] < rmax[j]) && p2 >= l) p2--;
		while((lmin[p1] > rmin[j] || lmax[p1] < rmax[j]) && p1 >= l) p1--;
		if(p2 < mid) res = (res + ((j * 2 - p2 - mid + 1) * (mid - p2 - 1) / 2) % mod * rmin[j] % mod * rmax[j] % mod) % mod;
		if(p1 > l) res = (res + _s1[p1] * j - s1[p1]) % mod;
		if(p1 >= p2) continue;
		if(lmin[p2] < rmin[j]) res = (res + ((_s2[p2] - _s2[p1]) * j - s2[p2] + s2[p1]) % mod * rmax[j] % mod) % mod;
		else res = (res + ((_s3[p2] - _s3[p1]) * j - s3[p2] + s3[p1]) % mod * rmin[j] % mod) % mod;
	}
	return (res % mod + mod) % mod;
}

signed main() {
	scanf("%lld", &n);
	for(int i = 1; i <= n; i++)
		scanf("%lld", &a[i]);
	printf("%lld\n", (solve(1, n) % mod + mod) % mod);
	
	return 0;
} 

不知道是贡献算错了还是什么