#include <bits/stdc++.h>
using namespace std;
constexpr int mod = 1e9;
int n, a[500005], ans = 0;
struct node {
	int l, r, sa1, sb1, sa2, sb2, ans1, ans2;
} tr[2000005];
struct tag {
	int a1, a2;
} lazy[2000005];
#define ls (p * 2)
#define rs (p * 2 + 1)
void pushup(int p) {
	tr[p].sa1 = (tr[ls].sa1 + tr[rs].sa1) % mod;
	tr[p].sb1 = (tr[ls].sb1 + tr[rs].sb1) % mod;
	tr[p].sa2 = (tr[ls].sa2 + tr[rs].sa2) % mod;
	tr[p].sb2 = (tr[ls].sb2 + tr[rs].sb2) % mod;
	tr[p].ans1 = (tr[ls].ans1 + tr[rs].ans1) % mod;
	tr[p].ans2 = (tr[ls].ans2 + tr[rs].ans2) % mod; 
}
void build(int p, int l, int r) {
	tr[p].l = l, tr[p].r = r;
	tr[p].sa1 = tr[p].sb1 = tr[p].sa2 = tr[p].sb2 = 0;
	tr[p].ans1 = tr[p].ans2 = 0;
	if (l == r) return ;
	int mid = (l + r) / 2;
	build(ls, l, mid), build(rs, mid + 1, r);
}
void add(int &x, int y) {
	x += y;
	if (x >= mod) x -= mod;
}
void add_tag(int p, tag t) {
	if (t.a1) {
		add(lazy[p].a1, t.a1);
		add(tr[p].ans1, 1ll * tr[p].sb1 * t.a1 % mod);
		add(tr[p].ans2, 1ll * tr[p].sb2 * t.a1 % mod);
		add(tr[p].sa1, 1ll * (tr[p].r - tr[p].l + 1) * t.a1 % mod);
		add(tr[p].sa2, 1ll * (tr[p].l + tr[p].r) * (tr[p].r - tr[p].l + 1) / 2 % mod * t.a1 % mod);
	}
	if (t.a2) {
		add(lazy[p].a2, t.a2);
		add(tr[p].ans1, 1ll * tr[p].sa1 * t.a2 % mod);
		add(tr[p].ans2, 1ll * tr[p].sa2 * t.a2 % mod);
		add(tr[p].sb1, 1ll * (tr[p].r - tr[p].l + 1) * t.a2 % mod);
		add(tr[p].sb2, 1ll * (tr[p].l + tr[p].r) * (tr[p].r - tr[p].l + 1) / 2 % mod * t.a2 % mod);
	}
}
void pushdown(int p) {
	if (lazy[p].a1 or lazy[p].a2) {
		add_tag(ls, lazy[p]);
		add_tag(rs, lazy[p]);
		lazy[p] = (tag){0, 0};
	}
}
void update(int p, int x, int y, tag t) {
	if (tr[p].l >= x && tr[p].r <= y) {
		return add_tag(p, t), void();
	}
	pushdown(p);
	int mid = (tr[p].l + tr[p].r) / 2;
	if (x <= mid) update(ls, x, y, t);
	if (mid < y) update(rs, x, y, t);
	pushup(p);
}
#undef ls
#undef rs
int main() {
	ios :: sync_with_stdio(0), cin.tie(0);
	cin >> n;
	for (int i = 1; i <= n; ++i) {
		cin >> a[i];
	}
	build(1, 1, n);
	stack <int> sta1, sta2;
	sta1.push(0), sta2.push(0);
	for (int i = 1; i <= n; ++i) {
		while (sta1.top() && a[ sta1.top() ] <= a[i]) {
			int x = sta1.top(), val = a[ sta1.top() ]; sta1.pop();
			update(1, sta1.top() + 1, x, (tag){a[i] - val, 0});
		}
		sta1.push(i), update(1, i, i, (tag){a[i], 0});
		while (sta2.top() && a[ sta2.top() ] >= a[i]) {
			int x = sta2.top(), val = a[ sta2.top() ]; sta2.pop();
			update(1, sta2.top() + 1, x, (tag){0, a[i] - val + mod});
		}
		sta2.push(i), update(1, i, i, (tag){0, a[i]});
		(ans += (1ll * tr[1].ans1 * (i + 1) % mod - tr[1].ans2 + mod) % mod) %= mod;
	}
	cout << ans << '\n';
	return 0;
}