//qoj6626
#include <bits/stdc++.h>
using namespace std; typedef long long ll;
void solve();int main(){ solve(); return 0; }

const int N = 1e6 + 10;
const ll P = 1e6 + 3;
int n, a[N], b[N];
tuple<int, int, int> q[N*2];
ll ans;

ll Sum(int x, int y){
	return (ll)y * (y-1) / 2 - (ll)x * (x-1) / 2;
}
int qrl(int x, int mn){
	int ans = 2e9;
	for(int i = x; i >= 1; -- i){
		if(a[i] > mn){
			ans = min(ans, a[i]);
		}
	}
	return ans;
}
int qrr(int x, int mn){
	int ans = 2e9;
	for(int i = x; i <= n; ++ i){
		if(a[i] > mn){
			ans = min(ans, a[i]);
		}
	}
	return ans;
}

void solve(){
	scanf("%d", &n);
	for(int i = 1; i <= n; ++ i){
		scanf("%d", &a[i]);
		q[i] = { a[i], i, -1 };
	}
	int mx = 0;
	for(int i = 1; i <= n; ++ i){
		mx = max(mx, a[i]);
		b[i] = mx;
	}
	mx = 0;
	for(int i = n; i >= 1; -- i){
		mx = max(mx, a[i]);
		b[i] = min(b[i], mx);
		q[i+n] = { b[i], i, 1 };
	}
	sort(q + 1, q + n + n + 1);
	set<int> st;
	for(int i = 1; i < n + n; ++ i){
		if(get<2>(q[i]) == -1){
			st.insert(get<1>(q[i]));
		} else {
			st.erase(get<1>(q[i]));
		}
		if(get<0>(q[i]) != get<0>(q[i+1]) && st.size()){
			int fr = get<0>(q[i]), to = get<0>(q[i+1]);
			int l = *st.begin(), r = *st.rbegin(), k = st.size();
			int oo = qrl(l, fr), pp = qrr(l, fr), qq = qrl(r, fr), rr = qrr(r, fr);
			int p = qrl(l, fr), q = qrr(r, fr);
			if(k == 1){
				ans += Sum(fr, to);
				ans += (oo + pp) * 1ll * (to - fr);
			} else {
				ans += (oo + rr + min(pp, qq) + k + k - 3) * 1ll * (to - fr);
				ans += 3 * (k - 1) * Sum(fr, to);
			}
			ans %= P;
		}
	}
	printf("%lld\n", ans);
}