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

typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 1e6 + 5;
const ll mod = 1e6 + 3;
const ll inf = 1e18 + 7;

set<int> st;
int h[maxn], pre[maxn], suf[maxn], n;
int p[maxn], b[maxn], id[maxn], id2[maxn], sz;
bool cmp(int x, int y) { return b[x] > b[y]; }
bool cmp2(int x, int y) { return h[x] > h[y]; }

#define ls k << 1
#define rs k << 1 | 1

struct segtree
{
	struct segnode
	{
		int l, r;
		ll mn;
	}t[maxn << 2];
	
	inline void pushup(int k) { t[k].mn = min(t[ls].mn, t[rs].mn); }
	void build(int k, int l, int r)
	{
		t[k].l = l, t[k].r = r;
		t[k].mn = inf;
		if (l == r) return;
		int mid = (l + r) >> 1;
		build(ls, l, mid);
		build(rs, mid + 1, r);
		pushup(k);
	}
	
	void update(int k, int x, ll d)
	{
		if (t[k].l == t[k].r)
		{
			t[k].mn = d;
			return;
		}
		int mid = (t[k].l + t[k].r) >> 1;
		if (x <= mid) update(ls, x, d);
		else update(rs, x, d);
		pushup(k);
	}
	
	ll query(int k, int l, int r)
	{
		if (l > r) return inf;
		if (l <= t[k].l && t[k].r <= r) return t[k].mn;
		int mid = (t[k].l + t[k].r) >> 1;
		ll ans = inf;
		if (l <= mid) ans = min(ans, query(ls, l, r));
		if (r > mid) ans = min(ans, query(rs, l, r));
		return ans;
	}
}T;
ll find(int x) { return T.query(1, 1, x - 1) + T.query(1, x + 1, n); }

ll calc(ll a, ll b, ll l, ll r)
{
	a %= mod, b %= mod;
	ll nw = (r - l + 1) % mod * b % mod;
	ll nw2 = (r - l + 1) * (l + r) / 2 % mod * a % mod;
	return (nw + nw2) % mod;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> h[i], pre[i] = max(pre[i - 1], h[i]), p[++sz] = h[i], id2[i] = i;
	for (int i = n; i; i--) suf[i] = max(suf[i + 1], h[i]);
	for (int i = 1; i <= n; i++) b[i] = min(pre[i], suf[i]), p[++sz] = b[i], id[i] = i;
	sort(p + 1, p + sz + 1);
	sort(id + 1, id + n + 1, cmp);
	sort(id2 + 1, id2 + n + 1, cmp2);
	sz = unique(p + 1, p + sz + 1) - p - 1;
	
	T.build(1, 1, n);
	ll ans = 0;
	for (int i = sz, j = 1, k = 1; i > 1; i--)
	{
		while (k <= n && b[id[k]] == p[i])
		{
			if (h[id[k]] != b[id[k]]) st.insert(id[k]);
			k++;
		}
		
		while (j <= n && h[id2[j]] == p[i])
		{
			if (h[id2[j]] != b[id2[j]]) st.erase(id2[j]);
			T.update(1, id2[j], h[id2[j]]);
			j++;
		}
		
		if (!st.size()) continue;
		if (st.size() == 1)
		{
			int x = *st.begin();
			(ans += calc(1, find(x), p[i - 1], p[i] - 1)) %= mod;
			continue;
		}
		
		int fir = *st.begin(), las = *st.rbegin();
		ll mnd = min(find(fir) + T.query(1, las + 1, n), find(las) + T.query(1, 1, fir - 1));
		(ans += calc((st.size() - 1) * 3, mnd + st.size() * 2 - 3, p[i - 1], p[i] - 1)) %= mod;
	}
	cout << ans;
	return 0;
}