#include <iostream>
#include <cstdio>
#define ll long long
#define inf 2000000000
#define mod 1000003
using namespace std;
int n,h[1000005];
int p,_h[1000005];
ll ans;
int main(){
	cin>>n;
	for (int i=1;i<=n;i++)scanf("%d",&h[i]);
	for (int i=1;i<=n;i++)
		if (p==0||h[i]>h[p])p=i;
	for (int i=1;i<=p;i++)_h[i]=max(h[i],_h[i-1]);
	for (int i=n;i>=p;i--)_h[i]=max(h[i],_h[i+1]);
	while(2333){
		int mn=inf,l=-1,r=-1,cnt=0;
		for (int i=1;i<=n;i++)
			if (h[i]!=_h[i]&&h[i]<mn)mn=h[i];
		if (mn==inf)break;
		for (int i=1;i<=n;i++)
			if (h[i]!=_h[i]&&h[i]==mn){
				if (l==-1)l=i;
				r=i;
				cnt++;
			}
		int vl=inf,vr=inf;
		for (int i=1;i<l;i++)
			if (h[i]>mn)vl=min(vl,h[i]);
		for (int i=r+1;i<=n;i++)
			if (h[i]>mn)vr=min(vr,h[i]);
		if (l==r){
			ans=(ans+mn+vl+vr)%mod;
			h[l]++;
			continue;
		}
		ans=(ans+vl+vr+min(vl,vr)+3ll*mn+1+1ll*(cnt-2)*(3*mn+2))%mod;
		for (int i=1;i<=n;i++)
			if (h[i]!=_h[i]&&h[i]==mn)h[i]++;
	}
	cout<<ans<<endl;
	return 0;
}