#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 v2;
int lazyUpd;
node(int ss, int ee):s(ss),e(ee),m((s+e)>>1),v(0),v2(1e15),lazyUpd(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;
}
forceProp();
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));
}
void self_add(int x){
v2+=x;
lazyUpd+=x;
}
void forceProp(){
if(s==e) return;
if(lazyUpd){
l->self_add(lazyUpd);
r->self_add(lazyUpd);
lazyUpd=0;
}
}
void rangeUpd(int x, int y, int c){
if(x<=s&&y>=e){
self_add(c);
return;
}
forceProp();
if(x<=m) l->rangeUpd(x,y,c);
if(y>m) r->rangeUpd(x,y,c);
v2=combine(l->v2,r->v2);
}
int query2(int x, int y){
if(x<=s&&y>=e){
return v2;
}
forceProp();
if(y<=m) return l->query2(x,y);
if(x>m) return r->query2(x,y);
return combine(l->query2(x,m),r->query2(m+1,y));
}
};
const int mod=1e6+3;
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);
}
vector<pii>pref;
pref.push_back({arr[0],0});
for(int x=1;x<n;x++){
if(arr[x]<pref.back().first){
st.rangeUpd(pref.back().second,x-1,pref.back().first);
pref.push_back({arr[x],x});
}
}
st.rangeUpd(pref.back().second,n-1,pref.back().first);
vector<pii>suf;
suf.push_back({arr[n-1],n-1});
for(int x=n-1;x>=0;x--){
if(arr[x]<suf.back().first){
st.rangeUpd(x+1,suf.back().second,suf.back().first);
suf.push_back({arr[x],x});
}
}
st.rangeUpd(0,suf.back().second,suf.back().first);
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+=(lft+rgt)*diff;
counter+=(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+=(lft+rgt)*diff+min(a,b)*diff+(dis[x]+dis[x-1]+1)*diff/2;
counter+=(dis[x]-1+dis[x-1])*diff/2*se.size();
counter%=mod;
}
else if(se.size()>2){
//int cost=0;
//show4(se,se);
//for(int y=0;y<n;y++){
//cout << st.query2(y,y) << " ";
//}
//cout << " st\n";
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);
int cost=(lft+rgt)*diff+min(a,b)*diff+(dis[x]+dis[x-1]+1)*diff/2;
cost+=(se.size()-2)*(dis[x]+dis[x-1]+1)*diff;
cost+=(dis[x]-1+dis[x-1])*diff/2*se.size();
//int hold=(lft+rgt)*diff+(dis[x]+dis[x-1]+1)*diff;
//hold+=(se.size()-3)*(dis[x]+dis[x-1]+1)*diff; //constant
//hold+=(dis[x]-1+dis[x-1])*diff/2*se.size(); //constant
//int take=st.query2(index+1,index2-1);
//show(take,take);
//hold+=take*diff;
//show2(cost,cost,hold,hold);
//cost=min(cost,hold);
//int cost2=1e15;
//auto it=se.begin();
//while(it!=prev(se.end())){
//int lft2=st.query(0,*it-1);
//int rgt2=st.query(*it+1,n-1);
//int hold=(lft+rgt)*diff+(dis[x]+dis[x-1]+1)*diff;
//hold+=(se.size()-3)*(dis[x]+dis[x-1]+1)*diff;
//hold+=(lft2+rgt2)*diff;
//hold+=(dis[x]-1+dis[x-1])*diff/2*se.size();
//cost2=min(cost2,hold);
//it++;
//}
//show(cost2,cost2);
counter+=cost;
counter%=mod;
}
for(auto it:storage[x]){
//st.upd(it,{1e15,-1e15});
st.upd(it,1e15);
st.rangeUpd(it,it,-1e15);
se.insert(it);
}
for(auto it:storage2[x]){
se.erase(se.find(it));
//st.upd(it,{1e15,1e15});
st.rangeUpd(it,it,1e15);
}
if(pref.back().first==dis[x]){
st.rangeUpd(pref.back().second,n-1,-pref.back().first);
pref.pop_back();
if(!pref.empty()){
st.rangeUpd(pref.back().second,n-1,pref.back().first);
}
}
if(suf.back().first==dis[x]){
st.rangeUpd(0,suf.back().second,-suf.back().first);
suf.pop_back();
if(!suf.empty()){
st.rangeUpd(0,suf.back().second,suf.back().first);
}
}
//show(counter,counter);
}
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();
}
}
