#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

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

int n;
int h[N];

int getmn(int l, int r, int x) {
	int ret = 1e9;
	for (int i = l; i < r; ++i) {
		if (h[i] > x) {
			ret = min(ret, h[i]);
		}
	}
	return ret;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n;
	for (int i = 0; i < n; ++i) {
		cin >> h[i];
	}
	int mx = 0;
	for (int i = 0; i < n; ++i) {
		mx = max(mx, h[i]);
	}
	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 += (((ll)kek.size()) - 2) * (x + x + 1 + x + 1);
		for (int i : kek) {
			++h[i];
		}
	}
	cout << ans << "\n";
	return 0;
}