#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 5e5+20,MOD = 1e9;//仅从题解学习分治思想，自己推的式子
long long sum[7][N];//7个前缀.zip
int a[N];
inline long long pf(long long d){
    return (d % MOD + MOD)%MOD;
}
long long solve(int l,int r){
    if(l == r){
        return a[l] * a[l] %MOD;
    }
    long long ans = 0;
    int mid = (l+r)/2;
    int p0 = mid+1,p1 = p0,p2 = p0;
    long long mi = a[p1],ma = a[p2];//这里自己的炸了一版,学题解写法p1p2分别最大最小
    while(p1<=r && mi >= a[mid]){
        mi = min(mi,(long long)a[p1]);
        p1++;
    }
    while(p2<=r && ma <= a[mid]){
        ma = max(ma,(long long)a[p2]);
        p2++;
    }
    long long ma2 = a[mid],mi2 = a[mid];
    for(int i = mid;i>=l;i--){
        mi2 = min(mi2,(long long)a[i]);
        ma2 = max(ma2,(long long)a[i]);
        while(p1<=r && mi >= mi2){
            mi = min(mi,(long long)a[p1]);
            p1++;
        }
        while(p2<=r && ma <= ma2){
            ma = max(ma,(long long)a[p2]);
            p2++;
        }
        if(p1 < p2){
            ans = (ans + mi2*ma2%MOD*pf(sum[6][p1-1] - sum[6][p0-1] - (i-1)*(p1 - p0)))%MOD;
            ans = (ans + ma2*pf(pf(sum[3][p2-1] - sum[3][p1-1]) - (i-1)*pf(sum[2][p2-1] - sum[2][p1-1])))%MOD;
            ans = (ans + pf(pf(sum[5][r] - sum[5][p2-1]) - (i-1)*pf(sum[4][r] - sum[4][p2-1])))%MOD;
        }else{
            ans = (ans + mi2*ma2%MOD*pf(sum[6][p2-1] - sum[6][p0-1] - (i-1)*(p2 - p0)))%MOD;
            ans = (ans + mi2*pf(pf(sum[1][p1-1] - sum[1][p2-1]) - (i-1)*pf(sum[0][p1-1] - sum[0][p2-1])))%MOD;
            ans = (ans + pf(pf(sum[5][r] - sum[5][p1-1]) - (i-1)*pf(sum[4][r] - sum[4][p1-1])))%MOD;
        }
    }
    return (ans + solve(l,mid) + solve(mid+1,r))%MOD;
}
signed main(){
    //freopen("main.in","r",stdin);
    int n;
    cin>>n;
    long long ma = -1,mi = 0x3f3f3f3f;
    for(int i = 1;i<=n;i++){
        cin>>a[i];
        ma = max((long long)a[i],ma);
        mi = min((long long)a[i],mi);
        sum[0][i] = (sum[0][i-1] + ma)%MOD;
        sum[1][i] = (sum[1][i-1] + i * ma%MOD)%MOD;
        sum[2][i] = (sum[2][i-1] + mi)%MOD;
        sum[3][i] = (sum[3][i-1] + i * mi%MOD)%MOD;
        sum[4][i] = (sum[4][i-1] + mi*ma%MOD)%MOD;
        sum[5][i] = (sum[5][i-1] + mi*ma%MOD*i%MOD)%MOD;
        sum[6][i] = (sum[6][i-1] + i)%MOD; 
    }
    cout<<solve(1,n)<<'\n';
}