# include <bits/stdc++.h>
using namespace std;
using ll=long long;
constexpr int mod=1e6+3;
int ans=0,a[1000010],b[1000010],X[1000010],mx1[1000010],mx2[1000010],le[1000010],ri[1000010],f[1000010][20],g[1000010][20],N;
set<int> st;
struct Event
{
	int v,x;
	Event()=default;
	Event(int v,int x):v(v),x(x){}
	bool operator<(const Event &t)const{return v<t.v;}
}c[2000010];
int calc(int n){return (ll)n*(n+1)/2%mod;}
int calc(int l,int r){return (calc(r)+mod-calc(l-1))%mod;}
void add(int &x,const auto &y){x=(x+y)%mod;}
int Qpre(int x,int v)// [1,x] : >=v
{
	if(le[v]<=x) return v;
	for(int i=__lg(N-v+1);i;i--)
		if(f[v][i] && le[f[v][i]]>x)
			v=f[v][i];
	return f[v][0];
}
int Qsuf(int x,int v)// [x,n] : >=v
{
	if(ri[v]>=x) return v;
	for(int i=__lg(N-v+1);i;i--)
		if(g[v][i] && ri[g[v][i]]<x)
			v=g[v][i];
	return g[v][0];
}
void work(int L,int R)
{
	int sz=st.size();
	if(!sz) return;
	int l=*st.begin(),r=*st.rbegin(),L1=X[Qpre(l-1,L+1)],L2=X[Qsuf(l+1,L+1)],R1=X[Qpre(r-1,L+1)],R2=X[Qsuf(r+1,L+1)];
	if(sz==1) add(ans,(ll)(L1+L2)*(X[R]-X[L])+calc(X[L],X[R]-1));
	else add(ans,(2ll*sz-3+L1+R2+(L1+L2<=R1+R2?L2:R1))*(X[R]-X[L])+3ll*(sz-1)*calc(X[L],X[R]-1));
}
int main()
{
	ios::sync_with_stdio(false);cin.tie(nullptr);
	int n,tot=0;
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i],X[i]=a[i];
	sort(X+1,X+n+1);
	N=unique(X+1,X+n+1)-X-1;
	for(int i=1;i<=n;i++) b[i]=lower_bound(X+1,X+N+1,a[i])-X;
	for(int i=n;i;i--) le[b[i]]=i;
	for(int i=1;i<=n;i++) ri[b[i]]=i;
	int tp=0;
	static int stk[1000010];
	for(int i=N;i;i--)
	{
		while(tp && le[stk[tp]]>le[i]) tp--;
		f[i][0]=stk[tp];stk[++tp]=i;
		for(int j=1;(1<<j)<=N-i;j++) f[i][j]=f[f[i][j-1]][j-1];
	}
	tp=0;
	for(int i=N;i;i--)
	{
		while(tp && ri[stk[tp]]<ri[i]) tp--;
		g[i][0]=stk[tp];stk[++tp]=i;
		for(int j=1;(1<<j)<=N-i;j++) g[i][j]=g[g[i][j-1]][j-1];
	}
	for(int i=1;i<=n;i++) mx1[i]=max(mx1[i-1],b[i]);
	for(int i=n;i;i--) mx2[i]=max(mx2[i+1],b[i]);
	for(int i=1;i<=n;i++)
		if(b[i]<min(mx1[i],mx2[i]))
			c[++tot]=Event(b[i],i),c[++tot]=Event(min(mx1[i],mx2[i]),-i);
	sort(c+1,c+tot+1);
	for(int i=1,j=1;i<=N;i++)
	{
		if(i>1) work(i-1,i);
		for(;j<=tot && c[j].v<=i;j++)
			if(c[j].x>0) st.insert(c[j].x);
			else st.erase(-c[j].x);
	}
	cout<<ans<<"\n";
	return 0;
}