#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int MAXN = 1e6 + 5;
const int mod = 1e6 + 3;
const int inf = 0x3f3f3f3f;

ll S1(ll l,ll r){ return (l+r) * (r-l+1) / 2 %mod;}

struct BIT
{
	int tree[MAXN], n;
	#define lowbit(x) ((x)&-(x))
	void update(int x,int k)
	{
		while(x<=n)
			tree[x] += k, x += lowbit(x);
	}
	int query(int x)
	{
		int res = 0;
		while(x)
			res += tree[x], x ^= lowbit(x);
		return res;
	}
	int kth(int k)
	{
		int res = 0;
		for(int i=1<<20; i; i>>=1)
			if(res+i<=n && tree[res+i]<k)
				res += i, k -= tree[res];
		return res + 1;
	}
}tpos;

namespace SegT
{
	const int N = 1<<20, SIZ = N * 2 + 5;
	int tree[SIZ];
	void push_up(int u)
	{
		tree[u] = min(tree[u<<1], tree[u<<1|1]);
	}
	void build(int *a,int n)
	{
		fill(tree+1, tree+2*N, inf);
		for(int i=1; i<=n; ++i)
			tree[N+i] = a[i];
		for(int i=N-1; i>=1; --i)
			push_up(i);
	}
	void set(int i,int k)
	{
		i += N;
		tree[i] = k;
		while(i >>= 1) push_up(i);
	}
	int getmn(int l,int r)
	{
		int res = inf;
		for(l+=N-1, r+=N+1; l^r^1; l>>=1, r>>=1)
		{
			if(~l&1) res = min(res, tree[l^1]);
			if( r&1) res = min(res, tree[r^1]);
		}
		return res;
	}
}

int h[MAXN];

int main(void)
{
	int n;
	scanf("%d",&n);
	for(int i=1; i<=n; ++i)
		scanf("%d",&h[i]);
	
	static int pre[MAXN], suf[MAXN];
	for(int i=1; i<=n; ++i)
		pre[i] = max(pre[i-1], h[i]);
	for(int i=n; i>=1; --i)
		suf[i] = max(suf[i+1], h[i]);
	
	tpos.n = n;
	SegT :: build(h, n);
	
	vector<pii> vec;
	for(int i=1; i<=n; ++i)
		vec.emplace_back(h[i], i);
	sort(vec.begin(), vec.end());
	
	int mx = *max_element(h+1, h+n+1);
	int l = 1, r = n;
	int ans = 0;
	for(int k=0; k<(int)vec.size(); ++k)
	{
		if(vec[k].first == mx) continue;
		
		tpos.update(vec[k].second, 1);
		SegT :: set(vec[k].second, inf);
		
		if(vec[k].first == vec[k+1].first) continue;
		
		while(pre[l] <= vec[k].first)
			tpos.update(l++, -1);
		while(suf[r] <= vec[k].first)
			tpos.update(r--, -1);
		
		int cnt = tpos.query(n);
		
		if(cnt == 0) continue;
		if(cnt == 1)
		{
			int x = tpos.kth(1);
			int vl = SegT :: getmn(1, x-1);
			int vr = SegT :: getmn(x+1, n);
			
			ll c0 = (vl + vr) %mod;
			ll c1 = 1;
			
			ans = ((ll)ans + c0 * (vec[k+1].first - vec[k].first)) %mod;
			ans = ((ll)ans + c1 * S1(vec[k].first, vec[k+1].first - 1)) %mod;
			continue;
		}
		
		int x = tpos.kth(1);
		int y = tpos.kth(cnt);
		
		int vl = SegT :: getmn(1, x-1);
		int vr = SegT :: getmn(y+1, n);
		int vmid = SegT :: getmn(1, n);
		
		ll c0 = ((ll)vl + vr + vmid + 1 + 2 * (cnt - 2)) %mod;
		ll c1 = ((ll)1 + 2 * (cnt - 2) + cnt) %mod;
		
		ans = ((ll)ans + c0 * (vec[k+1].first - vec[k].first)) %mod;
		ans = ((ll)ans + c1 * S1(vec[k].first, vec[k+1].first - 1)) %mod;
	}
	
	printf("%d\n",ans);
	return 0;
}