// iostream is too mainstream
#include <cstdio>
// bitch please
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <list>
#include <cmath>
#include <iomanip>
#define dibs reserve
#define OVER9000 1234567890
#define ALL_THE(CAKE,LIE) for(auto LIE =CAKE.begin(); LIE != CAKE.end(); LIE++)
#define tisic 47
#define soclose 1e-8
#define chocolate win
// so much chocolate
#define patkan 9
#define ff first
#define ss second
#define abs(x) ((x < 0)?-(x):x)
#define uint unsigned int
#define dbl long double
using namespace std;
// mylittledoge

long long mod =1000000000;

struct fin {
	vector<long long> T;
	fin(int N) {T.resize(N+1,0);}
	
	int lastone(int x) {return x&(x^(x-1));}
	
	void put(int pos, long long val) {
		for(int i =pos+1; i < T.size(); i +=lastone(i)) T[i] +=val;
		}

	long long get(int pos) {
		long long ret =0;
		for(int i =pos+1; i > 0; i -=lastone(i)) ret +=T[i];
		ret %=mod;
		if(ret < 0) ret +=mod;
		return ret;}
	};

struct info {
	int mi,mx,l;
	
	bool operator<(const info &A) const {
		return mi < A.mi;}
	};

long long solve(vector<int> &A, int z, int k) {
	if(z == k) return 0;
	if(z+1 == k) return (1LL*A[z]*A[z])%mod;
	long long ret =(solve(A,z,(z+k)/2)+solve(A,(z+k)/2,k))%mod;
	
	vector<info> V[2];
	int x =OVER9000, y =0, M =0;
	map<int,int> C;
	for(int i =(z+k)/2-1; i >= z; i--) {
		x =min(x,A[i]);
		y =max(y,A[i]);
		info I;
		I.mi =x, I.mx =y, I.l =(z+k)/2-i;
		C[y] =0;
		V[0].push_back(I);}
	x =OVER9000, y =0;
	for(int i =(z+k)/2; i < k; i++) {
		x =min(x,A[i]);
		y =max(y,A[i]);
		info I;
		I.mi =x, I.mx =y, I.l =i+1-(z+k)/2;
		C[y] =0;
		V[1].push_back(I);}
	// klesajuce v min
	ALL_THE(C,it) it->ss =M++;
	
	fin Fp(M+tisic), Fs(M+tisic), Ft(M+tisic), Fm(M+tisic);
	int a =0;
	for(int i =0; i < V[0].size(); i++) {
		while(a < V[1].size() && V[1][a].mi >= V[0][i].mi) {
			int c =C[V[1][a].mx];
			Fp.put(c,1);
			Fs.put(c,V[1][a].l);
			Fm.put(M-c,V[1][a].mx);
			Ft.put(M-c,(1LL*V[1][a].l*V[1][a].mx)%mod);
			a++;}
		int c =C[V[0][i].mx];
		long long q =(1LL*V[0][i].mi*V[0][i].mx)%mod;
		if(q < 0) q +=mod;
		long long d =(q*V[0][i].l)%mod;
		if(d < 0) d +=mod;
		long long e =(V[0][i].mi*V[0][i].l)%mod;
		if(e < 0) e +=mod;
		ret =(ret+1LL*d*Fp.get(c))%mod;
		ret =(ret+1LL*q*Fs.get(c))%mod;
		ret =(ret+1LL*e*Fm.get(M-1-c))%mod;
		ret =(ret+1LL*V[0][i].mi*Ft.get(M-1-c))%mod;}

	for(int i =0; i <= M+tisic; i++)
		Fp.T[i] =Ft.T[i] =Fs.T[i] =Fm.T[i] =0;
	a =0;
	for(int i =0; i < V[1].size(); i++) {
		while(a < V[0].size() && V[0][a].mi > V[1][i].mi) {
			int c =C[V[0][a].mx];
			Fp.put(c,1);
			Fs.put(c,V[0][a].l);
			Fm.put(M-c,V[0][a].mx);
			Ft.put(M-c,(1LL*V[0][a].l*V[0][a].mx)%mod);
			a++;}
		int c =C[V[1][i].mx];
		long long q =(1LL*V[1][i].mi*V[1][i].mx)%mod;
		if(q < 0) q +=mod;
		long long d =(q*V[1][i].l)%mod;
		if(d < 0) d +=mod;
		long long e =(V[1][i].mi*V[1][i].l)%mod;
		if(e < 0) e +=mod;
		ret =(ret+1LL*d*Fp.get(c))%mod;
		ret =(ret+1LL*q*Fs.get(c))%mod;
		ret =(ret+1LL*e*Fm.get(M-1-c))%mod;
		ret =(ret+1LL*V[1][i].mi*Ft.get(M-1-c))%mod;}
	
	if(ret < 0) ret +=mod;
	return ret;}

int main() {
	cin.sync_with_stdio(0);
	cin.tie(0);
	int N;
	cin >> N;
	vector<int> A(N);
	for(int i =0; i < N; i++) cin >> A[i];
	cout << solve(A,0,N) << "\n";
	return 0;}

// look at my code
// my code is amazing