#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll md = 1e6 + 3;
const int N = 1e6 + 7;

int n;
int h[N];
vector<int> byh[N];
int t[2 * N];

int getmn(int l, int r) {
	int ret = 1e9;
	for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
		if (l & 1) {
			ret = min(ret, t[l++]);
		}
		if (r & 1) {
			ret = min(ret, t[--r]);
		}
	}
	return ret;
}

void upd(int i) {
	i += n;
	t[i] = 1e9;
	for (; i > 1; i >>= 1) {
		t[i >> 1] = min(t[i], t[i ^ 1]);
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n;
	for (int i = 0; i < n; ++i) {
		cin >> h[i];
	}
	vector<int> hs;
	for (int i = 0; i < n; ++i) {
		hs.push_back(h[i]);
	}
	sort(hs.begin(), hs.end());
	hs.resize(unique(hs.begin(), hs.end()) - hs.begin());
	for (int i = 0; i < n; ++i) {
		int ind = lower_bound(hs.begin(), hs.end(), h[i]) - hs.begin();
		byh[ind].push_back(i);
	}
	for (int i = 0; i < n; ++i) {
		t[i + n] = h[i];
	}
	for (int i = n - 1; i > 0; --i) {
		t[i] = min(t[2 * i], t[2 * i + 1]);
	}
	set<int> good, bad;
	for (int i = 0; i < n; ++i) {
		good.insert(i);
	}
	ll ans = 0;
	int l = 0, r = n - 1;
	for (int i = 0; i < (int)hs.size() - 1; ++i) {
		int x = hs[i];
		int d = hs[i + 1] - hs[i];
		while (h[l] <= x) {
			++l;
		}
		while (h[r] <= x) {
			--r;
		}
		while (!good.empty() && *good.begin() < l) {
			upd(*good.begin());
			good.erase(good.begin());
		}
		while (!good.empty() && *good.rbegin() > r) {
			upd(*good.rbegin());
			good.erase(*good.rbegin());
		}
		for (int ind : byh[i]) {
			if (good.count(ind)) {
				upd(ind);
				good.erase(ind);
			}
			bad.insert(ind);
		}
		while (!bad.empty() && *bad.begin() < l) {
			bad.erase(bad.begin());
		}
		while (!bad.empty() && *bad.rbegin() > r) {
			bad.erase(*bad.rbegin());
		}
		// for (int i : bad) {
		// 	cout << i << " ";
		// }
		// cout << endl;
		if (bad.empty()) {
			continue;
		}
		if (bad.size() == 1) {
			int ind = *bad.begin();
			// cout << getmn(0, ind) << " " << getmn(ind + 1, n) << endl;
			ans += d * 1ll * (getmn(0, ind) + getmn(ind + 1, n));
			ans %= md;
			ans += x * 1ll * d;
			ans %= md;
			ans += d * 1ll * (d - 1) / 2;
			ans %= md;
			continue;
		}
		int cnt = bad.size();
		int ind1 = *bad.begin();
		int ind2 = *bad.rbegin();
		int mnl1 = getmn(0, ind1);
		int mnr1 = getmn(ind1 + 1, n);
		int mnl2 = getmn(0, ind2);
		int mnr2 = getmn(ind2 + 1, n);
		ans += d * 1ll * min((ll)mnl1 + mnr1 + mnr2, (ll)mnl2 + mnr2 + mnl1);
		ans %= md;
		ans += d;
		ans %= md;
		ans += x * 1ll * d % md * 3;
		ans %= md;
		ans += d * 1ll * (d - 1) / 2 % md * 3;
		ans %= md;
		ans += (cnt - 2) * 1ll * d % md * 2;
		ans %= md;
		ans += (cnt - 2) * 1ll * x % md * 3;
		ans %= md;
		ans += d * 1ll * (d - 1) / 2 % md * (cnt - 2) % md * 3;
		ans %= md;
	}
	cout << ans << "\n";
	// ll ans = 0;
	// for (int x = 1; x < mx; ++x) {
	// 	int l = 0;
	// 	while (h[l] <= x) {
	// 		++l;
	// 	}
	// 	int r = n - 1;
	// 	while (h[r] <= x) {
	// 		--r;
	// 	}
	// 	vector<int> kek;
	// 	for (int i = l + 1; i < r; ++i) {
	// 		if (h[i] == x) {
	// 			kek.push_back(i);
	// 		}
	// 	}
	// 	if (kek.empty()) {
	// 		continue;
	// 	}
	// 	if (kek.size() == 1) {
	// 		ans += x + getmn(0, kek[0], x) + getmn(kek[0] + 1, n, x);
	// 		ans %= md;
	// 		++h[kek[0]];
	// 		continue;
	// 	}
	// 	int mnl1 = getmn(0, kek[0], x);
	// 	int mnl2 = getmn(0, kek.back(), x);
	// 	int mnr1 = getmn(kek[0] + 1, n, x);
	// 	int mnr2 = getmn(kek.back() + 1, n, x);
	// 	ans += 2 * x + min(mnl1 + mnr1 + x + 1 + mnr2, mnl2 + mnr2 + mnl1 + x + 1);
	// 	ans %= md;
	// 	ans += (((ll)kek.size()) - 2) * (x + x + 1 + x + 1);
	// 	ans %= md;
	// 	for (int i : kek) {
	// 		++h[i];
	// 	}
	// }
	// cout << ans << "\n";
	return 0;
}