#pragma GCC optimize("O2")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <set>
#define mod 1000003
#define ll long long
using namespace std;

int n;
int a[1000005];
int b[1000005];
int mn[4000005];
int id[4000005];
set <int> st;
vector <int> g[1000005];

inline void in(int &n){
	n=0;
	char c=getchar();
	while(c<'0' || c>'9') c=getchar();
	while(c>='0'&&c<='9') n=n*10+c-'0',c=getchar();
	return ;
}

void build(int u,int l,int r){
	if(l==r){id[l]=u;return ;}
	int mid=(l+r)>>1;
	build(u<<1,l,mid);
	build(u<<1|1,mid+1,r);
	return ;
}

inline void updata(int u,int x){
	u=id[u];
	mn[u]=x;
	u>>=1;
	while(u){
		mn[u]=min(mn[u<<1],mn[u<<1|1]);
		u>>=1;
	}
	return ;
}

int query(int u,int l,int r,int L,int R){
	if(L<=l&&r<=R) return mn[u];
	int mid=(l+r)>>1,mnn=2e9;
	if(L<=mid) mnn=min(mnn,query(u<<1,l,mid,L,R));
	if(R>mid) mnn=min(mnn,query(u<<1|1,mid+1,r,L,R));
	return mnn;
}

void out(ll n){
	if(n>9) out(n/10);
	putchar(n%10+'0');
}

inline ll work(ll a,ll b){
	if(a%2==0) return (a/2)%mod*b%mod;
	return a%mod*((b/2)%mod)%mod;
}

signed main(){
	// freopen("repair.in","r",stdin);
	// freopen("repair.out","w",stdout);
	in(n);
	build(1,1,n);
	for(int i=1;i<=4*n;i++) mn[i]=2e9;
	for(int i=1;i<=n;i++) in(a[i]),b[i]=a[i],updata(i,a[i]);
	sort(b+1,b+1+n);
	int m=unique(b+1,b+1+n)-b-1;
	for(int i=1;i<=n;i++) g[lower_bound(b+1,b+1+m,a[i])-b].push_back(i);
	set <int> :: iterator it,ti;
	ll ans=0;
	for(int i=1;i<m;i++){
		for(int j:g[i]) updata(j,2e9),st.insert(j);
		it=st.begin();
		if((*it)==1) st.erase(it);
		if(st.empty()) continue;
		it=st.end();
		it--;
		if((*it)==n) st.erase(it);
		if(st.empty()) continue;
		it=st.begin();
		while(it!=st.end())
			if(max(query(1,1,n,1,*it),query(1,1,n,*it,n))>1e9) ti=it,it++,st.erase(ti);
			else break;
		if(st.empty()) continue;
		it=st.end();
		it--;
		while(it!=st.begin())
			if(max(query(1,1,n,1,*it),query(1,1,n,*it,n))>1e9) ti=it,it--,st.erase(ti);
			else break;
		if(st.empty()) continue;
		int l,r;
		it=st.begin();
		l=*it;
		it=st.end();
		it--;
		r=*it;
		int m1=query(1,1,n,1,l);
		int m2=query(1,1,n,l,n);
		int m3=query(1,1,n,1,r);
		int m4=query(1,1,n,r,n);
		ll s1=0,s2=0,x=mn[1];
		if(l==r){
			(ans+=1ll*(x-b[i])%mod*(m1+m2)%mod+work(b[i]+x-1,x-b[i]))%=mod;
			continue;
		}
		ll mm=min(m1+m2+m4,m1+m3+m4);
		(ans+=((x-b[i])%mod*mm%mod+(b[i]+x-1)%mod*(x-b[i])%mod+work(b[i]+x-1,x-b[i]))%mod)%=mod;
		(ans+=min(s1,s2))%=mod;
		ll tt=(ll)st.size()-2;
		(ans+=tt%mod*(b[i]+x+1)%mod*(x-b[i])%mod+tt*(work(b[i]+x-1,x-b[i]))%mod)%=mod;
	}
	printf("%lld\n",ans);

	return 0;
}
/*
10
72 33 22 22 13 49 53 57 72 85

10
4 1 2 5 4 5 1 2 9 5
*/