#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5, mod = 1e9;
struct node {
    int sm, sM, sL, smM, sML, smL, smML;
};
node operator+(node a, node b) {
    node c = {a.sm + b.sm,   a.sM + b.sM,   a.sL + b.sL,    a.smM + b.smM,
              a.sML + b.sML, a.smL + b.smL, a.smML + b.smML};
    return c;
}
struct LZ {
    int m, M, l;
};
node t[4 * N];
LZ lz[4 * N];
void downl(int id, int l, int r) {
    t[id].sL += 1ll * (lz[id].l * (r - l + 1)) % mod;
    t[id].sL %= mod;
    t[id].smL += 1ll * t[id].sm * lz[id].l % mod;
    t[id].smL %= mod;
    t[id].smML += 1ll * t[id].smM * lz[id].l % mod;
    if (l != r) {
        lz[id * 2].l += lz[id].l;
        lz[id * 2 + 1].l += lz[id].l;
        lz[id * 2].l %= mod;
        lz[id * 2 + 1].l %= mod;
    }
    lz[id].l = 0;
}
void downm(int id, int l, int r) {
    t[id].sm += 1ll * lz[id].m * (r - l + 1) % mod;
    t[id].sm %= mod;
    t[id].smM += 1ll * t[id].sM * lz[id].m % mod;
    t[id].smM %= mod;
    t[id].smML += 1ll * t[id].sML * lz[id].m % mod;
    t[id].smML %= mod;
    if (l != r) {
        lz[id * 2].m = lz[id].m;
        lz[id * 2 + 1].m = lz[id].m;
    }
    lz[id].m = 0;
}
void downM(int id, int l, int r) {
    t[id].sM += 1ll * lz[id].M * (r - l + 1) % mod;
    t[id].sM %= mod;
    t[id].smM += 1ll * t[id].sM * lz[id].M % mod;
    t[id].sm %= mod;
    t[id].smML += 1ll * t[id].smL * lz[id].M % mod;
    t[id].smML %= mod;
    lz[id].M = 0;
}
void down(int id, int l, int r) {
    downl(id, l, r);
    if (lz[id].m != 0) downm(id, l, r);
    if (lz[id].M != 0) downM(id, l, r);
}
void updatel(int id, int l, int r, int u, int v, int x) {
    down(id, l, r);
    if (r < u || v < l) return;
    if (u <= l && r <= v) {
        lz[id].l += x;
        down(id, l, r);
        return;
    }
    updatel(id * 2, l, (l + r) / 2, u, v, x);
    updatel(id * 2 + 1, (l + r) / 2 + 1, r, u, v, x);
    t[id] = t[id * 2] + t[id * 2 + 1];
}
void updatem(int id, int l, int r, int u, int v, int x) {
    down(id, l, r);
    if (r < u || v < l) return;
    if (u <= l && r <= v) {
        lz[id].m = x;
        down(id, l, r);
        return;
    }
    updatem(id * 2, l, (l + r) / 2, u, v, x);
    updatem(id * 2 + 1, (l + r) / 2 + 1, r, u, v, x);
    t[id] = t[id * 2] + t[id * 2 + 1];
}
void updateM(int id, int l, int r, int u, int v, int x) {
    down(id, l, r);
    if (r < u || v < l) return;
    if (u <= l && r <= v) {
        lz[id].M = x;
        down(id, l, r);
        return;
    }
    updateM(id * 2, l, (l + r) / 2, u, v, x);
    updateM(id * 2 + 1, (l + r) / 2 + 1, r, u, v, x);
    t[id] = t[id * 2] + t[id * 2 + 1];
}
int get(int id, int l, int r, int u, int v) {
    down(id, l, r);
    if (r < u || v < l) return 0;
    if (u <= l && r <= v) return t[id].smML;
    return (get(id * 2, l, (l + r) / 2, u, v) +
            get(id * 2 + 1, (l + r) / 2 + 1, r, u, v)) %
           mod;
}
int a[N];
signed main() {
    int n, pm, pM;
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    stack<int> sm, sM;
    int res = 0;
    for (int i = 1; i <= n; i++) {
        while (sm.size() && a[sm.top()] <= a[i]) sm.pop();
        if (sm.empty())
            pm = i;
        else
            pm = sm.top();
        sm.push(i);
        while (sM.size() && a[sM.top()] >= a[i]) sM.pop();
        if (sM.empty())
            pM = i;
        else
            pM = sM.top();
        sM.push(i);
        updatel(1, 1, n, 1, i, 1);
        updatem(1, 1, n, pm, i, a[i]);
        updateM(1, 1, n, pM, i, a[i]);
        res += get(1, 1, n, 1, i);
        res %= mod;
    }
    cout << res;
}