#include <bits/stdc++.h>
using namespace std;
const long long mod=1000003;
int n;
long long arr[1000005],ans;
struct node{
int s,e,m;
node *l,*r;
long long val;
node(int S, int E){
s=S; e=E; m=(s+e)/2;
if(s!=e){
l=new node(s,m);
r=new node(m+1,e);
val=min(l->val,r->val);
}
else val=arr[s];
}
void update(int S, long long V){
if(s==e){
val=V;
return;
}
if(S<=m) l->update(S,V);
else r->update(S,V);
val=min(l->val,r->val);
}
long long query(int S, int E){
if(S<=s&&e<=E) return val;
if(E<=m) return l->query(S,E);
else if(S>m) return r->query(S,E);
else return min(l->query(S,m),r->query(m+1,E));
}
} *root;
int32_t main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
pair<long long,int> hei[n+1];
for(int i=1; i<=n; i++) cin >> arr[i],hei[i]={arr[i],i};
sort(hei+1,hei+n+1);
root=new node(1,n);
long long mx[2][n+2];
mx[0][0]=0; mx[1][n+1]=0;
for(int i=1; i<=n; i++) mx[0][i]=max(mx[0][i-1],arr[i]);
for(int i=n; i>=1; i--) mx[1][i]=max(mx[1][i+1],arr[i]);
vector<pair<pair<long long,long long>,int> > up;
for(int i=1; i<=n; i++){
long long grr=min(mx[0][i],mx[1][i]);
if(grr>arr[i]){
up.push_back({{arr[i],grr},i});
ans+=(arr[i]+grr-1ll)*(grr-arr[i])/2ll%mod;
ans%=mod;
}
}
sort(up.begin(),up.end());
int cnt=0;
set<int> ind;
priority_queue<pair<long long,int>,vector<pair<long long,int> >,greater<pair<long long,int> > > pq;
for(int i=1; i<n; i++){
root->update(hei[i].second,1e16);
if(hei[i].first==hei[i+1].first) continue;
while(cnt<(int)up.size()&&hei[i].first==up[cnt].first.first){
ind.insert(up[cnt].second);
pq.push({up[cnt].first.second,up[cnt].second});
cnt++;
}
while(!pq.empty()&&pq.top().first==hei[i].first){
int x=pq.top().second;
pq.pop();
ind.erase(x);
}
if(ind.empty()) continue;
//cout << hei[i].first << '\n';
long long once=0;
once+=root->query(1,*ind.begin()-1);
//cout << root->query(1,*ind.begin()-1) << ' ';
once+=root->query(*(--ind.end())+1,n);
//cout << root->query(*(--ind.end())+1,n) << ' ';;
if((int)ind.size()>1){
once+=root->val;
//cout << root->val << ' ';
ans+=(((int)ind.size()-2ll)*2ll+1ll)*((hei[i].first+1ll+hei[i+1].first)*(hei[i+1].first-hei[i].first)/2ll%mod)%mod;
//cout << "grr " << (((int)ind.size()-2ll)*2ll+1ll)*((hei[i].first+1ll+hei[i+1].first)*(hei[i+1].first-hei[i].first)/2ll%mod)%mod << '\n';
ans%=mod;
}
//cout << '\n';
ans+=once*(hei[i+1].first-hei[i].first)%mod;
ans%=mod;
//cout << ans << '\n';
}
cout << ans;
}
