#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ld long double
#define show(x,y) cout << y << " " << #x << endl;
#define show2(x,y,i,j) cout << y << " " << #x << " " << j << " " << #i << endl;
#define show3(x,y,i,j,p,q) cout << y << " " << #x << " " << j << " " << #i << " " << q << " " << #p << endl;
#define show4(x,y) for(auto it:y) cout << it << " "; cout << #x << endl;
typedef pair<int,int>pii;
typedef pair<pii,int>pi2;
mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count());
inline int combine(int a, int b){
return min(a,b);
}
struct node{
int s,e,m;
node *l,*r;
int v;
int lazyUpd;
node(int ss, int ee):s(ss),e(ee),m((s+e)>>1),v(0){
if(s!=e){
l=new node(s,m);
r=new node(m+1,e);
}
}
void upd(int x, int y){
if(s==e){
v=y;
return;
}
if(x<=m) l->upd(x,y);
else r->upd(x,y);
v=combine(l->v,r->v);
}
int query(int x, int y){
if(x<=s&&y>=e){
return v;
}
if(y<=m) return l->query(x,y);
if(x>m) return r->query(x,y);
return combine(l->query(x,m),r->query(m+1,y));
}
};
const int mod=1e6+3;
int mul(int a, int b){
a%=mod; b%=mod;
return (a*b)%mod;
}
void solve(){
int n;
cin >> n;
int arr[n];
node st(0,n+5);
pii maxi={-1,-1};
vector<int>dis;
for(int x=0;x<n;x++){
cin >> arr[x];
st.upd(x,arr[x]);
dis.push_back(arr[x]);
maxi=max(maxi,{arr[x],x});
}
int target[n];
int cur=0;
for(int x=0;x<=maxi.second;x++){
cur=max(cur,arr[x]);
target[x]=cur;
}
cur=0;
for(int x=n-1;x>=maxi.second;x--){
cur=max(cur,arr[x]);
target[x]=cur;
}
sort(dis.begin(),dis.end());
dis.resize(unique(dis.begin(),dis.end())-dis.begin());
vector<int>storage[n+5];
vector<int>storage2[n+5];
for(int x=0;x<n;x++){
int a=lower_bound(dis.begin(),dis.end(),arr[x])-dis.begin();
int b=lower_bound(dis.begin(),dis.end(),target[x])-dis.begin();
storage[a].push_back(x);
storage2[b].push_back(x);
}
multiset<int>se;
int counter=0;
for(int x=0;x<n;x++){
//pull from previous
if(se.size()==1){
int diff=dis[x]-dis[x-1];
int index=*se.begin();
int lft=st.query(0,index-1);
int rgt=st.query(index+1,n-1);
counter+=mul(lft+rgt,diff);
counter%=mod;
counter+=mul((dis[x]-1+dis[x-1])*diff/2,se.size());
counter%=mod;
}
else if(se.size()==2){
int diff=dis[x]-dis[x-1];
int index=*se.begin();
int index2=*prev(se.end());
int lft=st.query(0,index-1);
int a=st.query(index+1,n-1);
int rgt=st.query(index2+1,n-1);
int b=st.query(0,index2-1);
counter+=mul(lft+rgt,diff);
counter%=mod;
counter+=mul(min(a,b),diff);
counter%=mod;
counter+=(dis[x]+dis[x-1]+1)*diff/2;
counter%=mod;
counter+=mul((dis[x]-1+dis[x-1])*diff/2,se.size());
counter%=mod;
}
else if(se.size()>2){
int diff=dis[x]-dis[x-1];
int index=*se.begin();
int index2=*prev(se.end());
int lft=st.query(0,index-1);
int a=st.query(index+1,n-1);
int rgt=st.query(index2+1,n-1);
int b=st.query(0,index2-1);
counter+=mul(lft+rgt,diff);
counter%=mod;
counter+=mul(min(a,b),diff);
counter%=mod;
counter+=(dis[x]+dis[x-1]+1)*diff/2;
counter%=mod;
counter+=mul((dis[x]+dis[x-1]+1)*diff,se.size()-2);
counter%=mod;
counter+=mul((dis[x]-1+dis[x-1])*diff/2,se.size());
counter%=mod;
}
for(auto it:storage[x]){
st.upd(it,1e15);
se.insert(it);
}
for(auto it:storage2[x]){
se.erase(se.find(it));
}
}
cout << counter;
}
int32_t main(){
ios::sync_with_stdio(0);
cin.tie(0);
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
int t=1;
//cin >> t;
while(t--){
solve();
}
}
