#include <iostream>
#include <fstream>
#include <cstdio>
#include <iomanip>
#include <utility>
#include <cstdlib>
#include <algorithm>
using namespace std;
const int N = 500500;
const int mod = 1000000000;
int n, a[N];
long long ans = 0;
int main ()
{

	scanf("%d", &n);
	
	for (int i = 1; i <= n; ++ i) {
		scanf("%d", &a[i]);
	}

	for (int i = 1; i <= n; ++ i) {
		int mn = a[i], mx = a[i];
		for (int j = i; j <= n; ++ j) {
			mn = min(mn, a[j]);
			mx = max(mx, a[j]);
			long long p = (mn * 1ll * mx) % mod;
			p = (p * (j - i + 1)) % mod;
			ans += p;
			if (ans >= mod) ans -= mod;
		}
	}

	cout << ans;

	return 0;
}