#include <iostream>
#include <cstdio>
#include <algorithm>
#define ll long long
#define inf 2000000000
#define mod 1000003
using namespace std;
int n,h[1000005];
int p,_h[1000005];
int qwq[1000005];
ll ans;
int gs(int l,int r){
	return 1ll*(l+r)*(r-l+1)/2%mod;
}
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]);
	for (int i=1;i<=n;i++)qwq[i]=h[i];
	sort(qwq+1,qwq+1+n);
	for (int t=1;t<n;t++){
		if (qwq[t]==qwq[t+1])continue;
		int mn=qwq[t],nxt=qwq[t+1],l=-1,r=-1,cnt=0;
		for (int i=1;i<=n;i++)
			if (h[i]!=_h[i]&&h[i]==mn){
				if (l==-1)l=i;
				r=i;
				cnt++;
			}
		if (cnt==0)continue;
		int vl=inf,vr=inf,xl=inf,xr=inf;
		for (int i=1;i<l;i++)
			if (h[i]>mn)vl=min(vl,h[i]);
		for (int i=l+1;i<=n;i++)
			if (h[i]>mn)xl=min(xl,h[i]);
		for (int i=n;i>r;i--)
			if (h[i]>mn)vr=min(vr,h[i]);
		for (int i=r-1;i>=1;i--)
			if (h[i]>mn)xr=min(xr,h[i]);
		if (l==r){
			ans=(ans+gs(mn,nxt-1)+vl+vr)%mod;
			h[l]=nxt;
			continue;
		}
		ans=(ans+vl+vr+min(xl,xr)+1+2ll*(cnt-2)+1ll*(cnt+1)*gs(mn,nxt-1))%mod;
		for (int i=1;i<=n;i++)
			if (h[i]!=_h[i]&&h[i]==mn)h[i]=nxt;
	}
	cout<<ans<<endl;
	return 0;
}