#include <iostream> #include <algorithm> #include <vector> #include <map> #include <set> using namespace std; int mod=1000003; map<int,vector<int> >event; int v[1000005]; int aint[2500005]; int inf=1e9,n; int pzst=1,pzdr; void update(int node,int st,int dr,int poz,int val) { if(st>poz || dr<poz) { return; } if(st==dr) { aint[node]=val; return; } int mij=(st+dr)/2; update(node*2,st,mij,poz,val); update(node*2+1,mij+1,dr,poz,val); aint[node]=min(aint[node*2],aint[node*2+1]); } int query(int node,int st,int dr,int qst,int qdr) { if(st>qdr || st>dr || qst>dr || qst>qdr) { return inf; } if(qst<=st && dr<=qdr) { return aint[node]; } int mij=(st+dr)/2; return min(query(node*2,st,mij,qst,qdr),query(node*2+1,mij+1,dr,qst,qdr)); } set<int>s0; void update(int poz) { s0.insert(poz); update(1,1,n,poz,inf); } long long gaus(int a) { return (a*(a+1)/2)%mod; } long long recalc(int val,int iter) { while(s0.size() && *s0.begin()==pzst) { s0.erase(s0.begin()); pzst++; } while(s0.size() && *prev(s0.end())==pzdr) { s0.erase(prev(s0.end())); pzdr--; } if(s0.size()==0) { return 0; } int minimpref=query(1,1,n,1,*s0.begin()); int minimsuf=query(1,1,n,*prev(s0.end()),n); int minimtot=query(1,1,n,1,n); if(s0.size()==1) { return ((minimpref+minimsuf)*iter+gaus(val+iter-1)-gaus(val-1))%mod; } return ((minimpref+minimsuf+minimtot)*iter+s0.size()*(gaus(val+iter-1)-gaus(val-1))+(s0.size()*2-3)*(gaus(val+iter)-gaus(val)))%mod; } signed main() { long long i,j,k,l,t,h,w,x,m,a,b; ios_base::sync_with_stdio(false); cin.tie(NULL); cin>>n; pzdr=n; for(long long i=1;i<=n;i++) { cin>>v[i]; event[v[i]].push_back(i); update(1,1,n,i,v[i]); } long long tot=0; for(auto it=event.begin();it!=event.end();it++) { for(auto k:it->second) { update(k); } auto it2=it; it2++; if(it2!=event.end()) { tot=(tot+recalc(it->first,(it2->first-it->first)))%mod; } } cout<<tot%mod; return 0; }