# include <bits/stdc++.h>
using namespace std;
const int mod=1e6+3;
typedef long long ll;
int n,len,a[1000010],b[1000010],L[1000010],R[1000010],stk[1000010],pre[1000010][20],suf[1000010][20],lim[1000010];
vector<int> pos[1000010];
set<int> st;
int S(int l,int r){return (ll)(l+r)*(r-l+1)/2%mod;}
int queryl(int p,int x) // min { i : i >= x , L[i] <= p }
{
	if(L[x]<=p) return x;
	for(int i=19;i>=0;i--)
		if(pre[x][i]>=1 && L[pre[x][i]]>p) x=pre[x][i];
	return pre[x][0];
}
int queryr(int p,int x) // min { i : i >= x , R[i] >= p }
{
	if(R[x]>=p) return x;
	for(int i=19;i>=0;i--)
		if(suf[x][i]<=len && R[suf[x][i]]<p) x=suf[x][i];
	return suf[x][0];
}
int main()
{
	int tp=0,ans=0;
	cin>>n;
	for(int i=1;i<=n;i++) scanf("%d",&a[i]),b[++len]=a[i];
	sort(b+1,b+len+1);
	len=unique(b+1,b+len+1)-b-1;
	for(int i=1;i<=n;i++) a[i]=lower_bound(b+1,b+len+1,a[i])-b,pos[a[i]].push_back(i);
	for(int i=1;i<=len;i++) L[i]=pos[i].front(),R[i]=pos[i].back();
	for(int i=1;i<=len;i++)
	{
		while(tp && L[stk[tp]]>=L[i]) tp--;
		pre[i][0]=stk[tp];stk[++tp]=i;
	}
	tp=0;stk[0]=len+1;suf[len+1][0]=len+1;
	for(int i=len;i>=1;i--)
	{
		while(tp && R[stk[tp]]<=R[i]) tp--;
		suf[i][0]=stk[tp];stk[++tp]=i;
	}
	for(int i=0;i<=len;i++)
		for(int j=1;j<=19;j++)
			pre[i][j]=pre[pre[i][j-1]][j-1];
	for(int i=len+1;i>=1;i--)
		for(int j=1;j<=19;j++)
			suf[i][j]=suf[suf[i][j-1]][j-1];
	fill(lim+1,lim+n+1,len);
	for(int i=1,mx=0;i<=n;i++) lim[i]=min(lim[i],mx),mx=max(mx,a[i]);
	for(int i=n,mx=0;i>=1;i--) lim[i]=min(lim[i],mx),mx=max(mx,a[i]);
	for(int i=1;i<len;i++)
	{
		for(int j:pos[i]) st.insert(j);
		auto chk=[&](int p){return lim[p]<=i;};
		while(!st.empty() && chk(*st.begin())) st.erase(st.begin());
		while(!st.empty() && chk(*--st.end())) st.erase(--st.end());
		if(st.empty()) continue;
		int l=*st.begin(),r=*--st.end(),cnt=st.size();
		ans=(ans+(ll)cnt*S(b[i],b[i+1]-1))%mod;
		ans=(ans+(ll)(b[queryl(l-1,i+1)]+b[queryr(r+1,i+1)])*(b[i+1]-b[i]))%mod;
		if(cnt>1)
		{
			ans=(ans+(2ll*cnt-3)*S(b[i]+1,b[i+1]))%mod;
			ans=(ans+(ll)b[min(queryr(l+1,i+1),queryl(r-1,i+1))]*(b[i+1]-b[i]))%mod;
		}
	}
	cout<<ans<<endl;
	return 0;
}