/*
  author: honglan0301
  Sexy_goodier _ xiaoqing
 */
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <cctype>
#include <queue>
#include <map>
#include <unordered_map>
#include <cstdlib>
#include <ctime>
#include <vector>
#include <cmath>
#include <random>
#include <set>
#include <bitset>
#include <assert.h>
using namespace std;

//namespace Fread{const int SIZE=1<<20;char buf[SIZE],*S,*T;inline char getchar(){if(S==T){T=(S=buf)+fread(buf,1,SIZE,stdin);if(S==T)return'\n';}return*S++;}}using namespace Fread;namespace Fwrite{const int SIZE=1<<20;char buf[SIZE],*S=buf,*T=buf+SIZE;inline void flush(){fwrite(buf,1,S-buf,stdout);S=buf;}inline void putchar(char c){*S++=c;if(S==T)flush();}struct NTR{~NTR(){flush();}}ztr;}using namespace Fwrite;
//#define getchar Fread::getchar
//#define putchar Fwrite::putchar

namespace Fastio{struct Reader{template<typename T>Reader&operator>>(T&x){x=0;short f=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-')f*=-1;c=getchar();}while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();x*=f;return*this;}Reader&operator>>(double&x){x=0;double t=0;short f=1,s=0;char c=getchar();while((c<'0'||c>'9')&&c!='.'){if(c=='-')f*=-1;c=getchar();}while(c>='0'&&c<='9'&&c!='.')x=x*10+(c^48),c=getchar();if(c=='.')c=getchar();else{x*=f;return*this;}while(c>='0'&&c<='9')t=t*10+(c^48),s++,c=getchar();while(s--)t/=10.0;x=(x+t)*f;return*this;}Reader&operator>>(long double&x){x=0;long double t=0;short f=1,s=0;char c=getchar();while((c<'0'||c>'9')&&c!='.'){if(c=='-')f*=-1;c=getchar();}while(c>='0'&&c<='9'&&c!='.')x=x*10+(c^48),c=getchar();if(c=='.')c=getchar();else{x*=f;return*this;}while(c>='0'&&c<='9')t=t*10+(c^48),s++,c=getchar();while(s--)t/=10.0;x=(x+t)*f;return*this;}Reader&operator>>(__float128&x){x=0;__float128 t=0;short f=1,s=0;char c=getchar();while((c<'0'||c>'9')&&c!='.'){if(c=='-')f*=-1;c=getchar();}while(c>='0'&&c<='9'&&c!='.')x=x*10+(c^48),c=getchar();if(c=='.')c=getchar();else{x*=f;return*this;}while(c>='0'&&c<='9')t=t*10+(c^48),s++,c=getchar();while(s--)t/=10.0;x=(x+t)*f;return*this;}Reader&operator>>(char&c){c=getchar();while(c==' '||c=='\n'||c=='\r')c=getchar();return*this;}Reader&operator>>(char*str){int len=0;char c=getchar();while(c==' '||c=='\n'||c=='\r')c=getchar();while(c!=' '&&c!='\n'&&c!='\r')str[len++]=c,c=getchar();str[len]='\0';return*this;}Reader&operator>>(string&str){str.clear();char c=getchar();while(c==' '||c=='\n'||c=='\r')c=getchar();while(c!=' '&&c!='\n'&&c!='\r')str.push_back(c),c=getchar();return*this;}Reader(){}}cin;const char endl='\n';struct Writer{const int Setprecision=6;typedef int mxdouble;template<typename T>Writer&operator<<(T x){if(x==0){putchar('0');return*this;}if(x<0)putchar('-'),x=-x;static short sta[40];short top=0;while(x>0)sta[++top]=x%10,x/=10;while(top>0)putchar(sta[top]+'0'),top--;return*this;}Writer&operator<<(double x){if(x<0)putchar('-'),x=-x;mxdouble _=x;x-=(double)_;static short sta[40];short top=0;while(_>0)sta[++top]=_%10,_/=10;if(top==0)putchar('0');while(top>0)putchar(sta[top]+'0'),top--;putchar('.');for(int i=0;i<Setprecision;i++)x*=10;_=x;while(_>0)sta[++top]=_%10,_/=10;for(int i=0;i<Setprecision-top;i++)putchar('0');while(top>0)putchar(sta[top]+'0'),top--;return*this;}Writer&operator<<(long double x){if(x<0)putchar('-'),x=-x;mxdouble _=x;x-=(long double)_;static short sta[40];short top=0;while(_>0)sta[++top]=_%10,_/=10;if(top==0)putchar('0');while(top>0)putchar(sta[top]+'0'),top--;putchar('.');for(int i=0;i<Setprecision;i++)x*=10;_=x;while(_>0)sta[++top]=_%10,_/=10;for(int i=0;i<Setprecision-top;i++)putchar('0');while(top>0)putchar(sta[top]+'0'),top--;return*this;}Writer&operator<<(__float128 x){if(x<0)putchar('-'),x=-x;mxdouble _=x;x-=(__float128)_;static short sta[40];short top=0;while(_>0)sta[++top]=_%10,_/=10;if(top==0)putchar('0');while(top>0)putchar(sta[top]+'0'),top--;putchar('.');for(int i=0;i<Setprecision;i++)x*=10;_=x;while(_>0)sta[++top]=_%10,_/=10;for(int i=0;i<Setprecision-top;i++)putchar('0');while(top>0)putchar(sta[top]+'0'),top--;return*this;}Writer&operator<<(char c){putchar(c);return*this;}Writer&operator<<(char*str){int cur=0;while(str[cur])putchar(str[cur++]);return*this;}Writer&operator<<(const char*str){int cur=0;while(str[cur])putchar(str[cur++]);return*this;}Writer&operator<<(string str){int st=0,ed=str.size();while(st<ed)putchar(str[st++]);return*this;}Writer(){}}cout;}using namespace Fastio;
#define cin Fastio::cin
#define cout Fastio::cout
#define endl Fastio::endl//;fflush(stdout)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define int long long
#define ull unsigned long long
#define mod 1000003
mt19937 rnd(time(0));
mt19937_64 rndl(time(0));

int n,h[1000005],fl,fr,mx,c[1000005],cntc,qmx[1000005],hmx[1000005],ans;
vector <int> in[1000005],ot[1000005];
set <int> ss;

struct tree
{
	int ls,rs,cnt;
}tree[30000005];
int rt[1000005],cntd;

#define ls(x) tree[x].ls
#define rs(x) tree[x].rs
#define n(x) tree[x].cnt
#define t(x) tree[x]
#define md(x,y) ((x+y)>>1)
#define push_up(x) n(x)=n(ls(x))+n(rs(x))

int cz(int l,int r,int x,int k,int q,int p)
{
	p=++cntd; t(p)=t(q); if(l==r) return n(p)+=k,p; int mid=md(l,r);
	if(mid>=x) ls(p)=cz(l,mid,x,k,ls(q),ls(p)); else rs(p)=cz(mid+1,r,x,k,rs(q),rs(p)); return push_up(p),p;
}
int askm(int l,int r,int q,int p)
{
	if(n(p)-n(q)==0) return 0; if(l==r) return l; int mid=md(l,r);
	if(n(ls(p))-n(ls(q))>0) return askm(l,mid,ls(q),ls(p)); else return askm(mid+1,r,rs(q),rs(p));
}
int askm(int l,int r,int x,int y,int q,int p)
{
	if(l>=x&&r<=y) return askm(l,r,q,p); int mid=md(l,r),na=0;
	if(mid>=x) na=askm(l,mid,x,y,ls(q),ls(p)); if(na) return na; if(mid<y) na=askm(mid+1,r,x,y,rs(q),rs(p)); return na;
}

void init() {for(int i=1;i<=n;i++) rt[i]=cz(1,cntc,h[i],1,rt[i-1],rt[i]);}
int askl(int x,int k) {return askm(1,cntc,k+1,cntc,rt[0],rt[x]);}
int askr(int x,int k) {return askm(1,cntc,k+1,cntc,rt[x],rt[n]);}
int calc(int l,int r) {return (l+r)*(r-l+1)/2%mod;}

signed main()
{
	cin>>n; for(int i=1;i<=n;i++) cin>>h[i],mx=max(mx,h[i]),c[i]=h[i];
	fl=10000000; fr=0; for(int i=1;i<=n;i++) if(h[i]==mx) fl=min(fl,i),fr=max(fr,i);
	sort(c+1,c+n+1); cntc=unique(c+1,c+n+1)-c-1; for(int i=1;i<=n;i++) h[i]=lower_bound(c+1,c+cntc+1,h[i])-c;
	for(int i=1;i<=n;i++) qmx[i]=max(qmx[i-1],h[i]); for(int i=n;i>=1;i--) hmx[i]=max(hmx[i+1],h[i]);
	for(int i=1;i<=n;i++) (i<fl)?in[h[i]].pb(i),ot[qmx[i]].pb(i):in[h[i]].pb(i),ot[hmx[i]].pb(i); init();
	for(int i=1;i<=cntc;i++)
	{
		for(auto j:in[i]) ss.insert(j); for(auto j:ot[i]) ss.erase(j);
		if(!ss.size()) continue;
		else if(ss.size()==1)
		{
			int nr=(*ss.begin()); ans+=(c[i+1]-c[i])%mod*(c[askl(nr,i)]+c[askr(nr,i)])%mod,ans%=mod;
			//cout<<i<<" "<<c[i]<<" "<<nr<<" "<<ans<<" "<<askl(nr,i)<<" "<<askr(nr,i)<<endl;
			ans+=calc(c[i],c[i+1]-1); ans%=mod;
		}
		else
		{
			int nl=(*ss.begin()),nr=(*(--ss.end()));
			int tol=c[askl(nl,i)],tor=c[askr(nr,i)]; ans+=(c[i+1]-c[i])%mod*(tol+tor+min(tol,tor))%mod,ans%=mod;
			ans+=2ll*calc(c[i],c[i+1]-1); ans%=mod; ans+=2ll*((int)ss.size()-2)*calc(c[i]+1,c[i+1]); ans%=mod;
		}
	}
	cout<<ans<<endl;
}