#include <iostream> #include <algorithm> #include <vector> #include <map> #include <set> using namespace std; long long mod=1000003; map<long long,vector<long long> >event; long long v[1000005]; long long aint[2500005]; long long inf=2e9,n; long long pzst=1,pzdr; void update(long long node,long long st,long long dr,long long poz,long long val) { if(st>poz || dr<poz) { return; } if(st==dr) { aint[node]=val; return; } long long 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]); } long long query(long long node,long long st,long long dr,long long qst,long long qdr) { if(st>qdr || st>dr || qst>dr || qst>qdr) { return inf; } if(qst<=st && dr<=qdr) { return aint[node]; } long long mij=(st+dr)/2; return min(query(node*2,st,mij,qst,qdr),query(node*2+1,mij+1,dr,qst,qdr)); } set<long long>s0; void update(long long poz) { s0.insert(poz); update(1,1,n,poz,inf); } long long gaus(long long a) { return (a*(a+1)/2)%mod; } long long recalc(long long val,long long 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; } long long minimpref=query(1,1,n,1,*s0.begin())%mod; long long minimsuf=query(1,1,n,*prev(s0.end()),n)%mod; long long minimtot=query(1,1,n,1,n)%mod; if(s0.size()==1) { return ((minimpref+minimsuf)*iter+gaus(val+iter-1)-gaus(val-1)+mod)%mod; } return ((minimpref+minimsuf+minimtot)*iter+s0.size()*(gaus(val+iter-1)-gaus(val-1)+mod)+(s0.size()*2-3)*(gaus(val+iter)-gaus(val)+mod))%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; }