#include <iostream>
#include <algorithm>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<vector>
#include<iomanip>
#include<ctime>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<bitset>
#include<cassert>
#define sqr(x) ((x)*(x))
#define fz1(i,n) for ((i)=1;(i)<=(n);(i)++)
#define fd1(i,n) for ((i)=(n);(i)>=1;(i)--)
#define fz0g(i,n) for ((i)=0;(i)<=(n);(i)++)
#define fd0g(i,n) for ((i)=(n);(i)>=0;(i)--)
#define fz0k(i,n) for ((i)=0;(i)<(n);(i)++)
#define fd0k(i,n) for ((i)=(((long long)(n))-1);(i)>=0;(i)--)
#define fz(i,x,y) for ((i)=(x);(i)<=(y);(i)++)
#define fd(i,y,x) for ((i)=(y);(i)>=(x);(i)--)
#define fzin fz1(i,n)
#define fzim fz1(i,m)
#define fzjn fz1(j,n)
#define fzjm fz1(j,m)
#define ff(c,itr) for (__typeof((c).begin()) itr=(c).begin();itr!=(c).end();++itr)
#define pb push_back
#define mk make_pair
#define rdst(st,len){static char ss[len];scanf(" %s",ss);(st)=ss;}
#define spln(i,n) (i==n?'\n':' ')
#define fac_init(n){fac[0]=fac[1]=inv[1]=fi[0]=fi[1]=1;fz(i,2,n){fac[i]=1ll*fac[i-1]*i%mod;inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;fi[i]=1ll*fi[i-1]*inv[i]%mod;}}
using namespace std;
typedef long long i64;
typedef long double f80;
typedef unsigned int u32;
typedef unsigned long long u64;
//typedef __int128 i128;
//typedef unsigned __int128 u128;
#ifndef ONLINE_JUDGE
	FILE *___=freopen("1.in","r",stdin);
#endif
inline void read(int &x)
{
	char c;int f=1;
	while(!isdigit(c=getchar()))if(c=='-')f=-1;
	x=(c&15);while(isdigit(c=getchar()))x=(x<<1)+(x<<3)+(c&15);
	x*=f;
}
const int mod=1e6+3;
int n,m,i,j,a[1000005],b[1000005],c[1000005],ans;
vector<int> all;
int pre[1000005],suf[1000005],cnt,lc[40000005],rc[40000005];
int nwnd(int x){cnt++;lc[cnt]=lc[x];rc[cnt]=rc[x];return cnt;}
void update(int &x,int l,int r,int y)
{
	x=nwnd(x);if(l==r)return;int mid=(l+r)/2;
	if(y<=mid)update(lc[x],l,mid,y);else update(rc[x],mid+1,r,y);
}
int query(int x,int l,int r,int ql)
{
	if(r<ql||!x) return r+1;if(l==r) return l;
	int mid=(l+r)/2,t=query(lc[x],l,mid,ql);
	if(t<=mid)return t;return query(rc[x],mid+1,r,ql);
}
vector<int> vi[1000005],vo[1000005];
set<int> s;
int main()
{
	read(n);fz1(i,n)read(a[i]),all.push_back(a[i]);
	sort(all.begin(),all.end());all.resize(unique(all.begin(),all.end())-all.begin());fz1(i,n)a[i]=upper_bound(all.begin(),all.end(),a[i])-all.begin();
	fz1(i,n)b[i]=max(b[i-1],a[i]);fd1(i,n)c[i]=max(c[i+1],a[i]);fz1(i,n)b[i]=min(b[i],c[i]);
	fz1(i,n)pre[i]=pre[i-1],update(pre[i],1,all.size(),a[i]);fd1(i,n)suf[i]=suf[i+1],update(suf[i],1,all.size(),a[i]);
	fz1(i,n)if(a[i]!=b[i])vi[a[i]].push_back(i),vo[b[i]].push_back(i);
	fz1(i,all.size()){
		ff(vi[i],it) s.insert(*it);
		ff(vo[i],it) s.erase(*it);
		if(s.empty()) continue;
		ans=(ans+1ll*(all[i-1]+all[i]-1)*(all[i]-all[i-1])/2%mod*(s.size()))%mod;
		if(s.size()==1){
			int x=*s.begin();
			int l=query(pre[x],1,all.size(),i+1),r=query(suf[x],1,all.size(),i+1);
			ans=(ans+all[l-1]+all[r-1])%mod;
			continue;
		}
		int x=*s.begin(),y=*s.rbegin();
		int l1=query(pre[x],1,all.size(),i+1),r1=query(suf[x],1,all.size(),i+1);
		int l2=query(pre[y],1,all.size(),i+1),r2=query(suf[y],1,all.size(),i+1);
		ans=(ans+1ll*min(all[l1-1]+all[r1-1]+all[r2-1],all[l2-1]+all[r2-1]+all[l1-1])*(all[i]-all[i-1]))%mod;
		ans=(ans+1ll*(all[i-1]+1+all[i])*(all[i]-all[i-1])/2%mod*(s.size()+s.size()-3))%mod;
	}
	printf("%d\n",ans);
	return 0;
}