#include <bits/stdc++.h>
using namespace std;

void just_do_it();

int main() {
	#ifdef KAMIRULEZ
		freopen("kamirulez.inp", "r", stdin);
		freopen("kamirulez.out", "w", stdout);
	#endif
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	just_do_it();
	return 0;
}

const int inf = 1e9 + 20;
const int maxn = 1e6 + 20;
const long long mod = 1e6 + 3;
int a[maxn];
int vals[maxn];
int pref[maxn];
int suf[maxn];
bool flag[maxn];
vector<int> groups[maxn];
pair<int, int> order[maxn];
int n;

int get_pref(int val, int rt) {
	int res = inf;
	for (int i = 1; i <= rt; i++) {
		if (a[i] > val) {
			res = min(res, a[i]);
		}
	}
	return res;
}

int get_suf(int val, int lt) {
	int res = inf;
	for (int i = lt; i <= n; i++) {
		if (a[i] > val) {
			res = min(res, a[i]);
		}
	}
	return res;
}

void just_do_it() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		order[i] = {a[i], i};
	}
	for (int i = 1; i <= n; i++) {
		pref[i] = max(a[i], pref[i - 1]);
		suf[i] = max(a[n + 1 - i], suf[i - 1]);
	}
	sort(order + 1, order + n + 1);
	int m = 0;
	for (int i = 1; i <= n; i++) {
		if (order[i].first != order[i - 1].first) {
			vals[++m] = order[i].first;
		}
		groups[m].push_back(order[i].second);
	}
	int lt1 = 1;
	int rt1 = n;
	long long res = 0;
	set<int> pos;
	for (int i = 1; i <= m - 1; i++) {
		for (auto x: groups[i]) {
			pos.insert(x);
		}
		while (!pos.empty() && *pos.begin() == lt1) {
			pos.erase(pos.begin());
			lt1++;
		}
		while (!pos.empty() && *pos.rbegin() == rt1) {
			pos.erase(prev(pos.end()));
			rt1--;
		}
		if (pos.empty()) {
			continue;
		}
		int lt2 = *pos.begin();
		int rt2 = *pos.rbegin();
		int cnt = pos.size();
		long long cost = (get_pref(vals[i], lt2) + get_suf(vals[i], rt2)) % mod;
		if (cnt > 1) {
			cost = (cost + min(get_suf(vals[i], lt2), get_pref(vals[i], rt2)) + cnt * 2 - 3) % mod;
		}
		long long sum = (1LL * (vals[i + 1] + vals[i] - 1) * (vals[i + 1] - vals[i]) / 2) % mod;
		res = (res + cost * (vals[i + 1] - vals[i])) % mod;
		res = (res + sum * cnt % mod);
	}
	cout << res;
}