#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef vector<P> vp;
typedef vector<vp> vvp;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define REP(i,k,n) for(ll i=(ll)(k);i<(ll)(n);i++)
#define all(a) a.begin(),a.end()
#define fi first
#define se second
#define pb emplace_back
#define dupli(a) {sort(all(a));a.erase(unique(all(a)),a.end());}
#define lb(v,k) (lower_bound(all(v),k)-v.begin())
template<class T> bool chmin(T&a,T b){if(a>b){a=b;return true;}return false;}
template<class T> bool chmax(T&a,T b){if(a<b){a=b;return true;}return false;}
template<class T> void out(T a){cout<<a<<'\n';}
template<class T> void outv(T v){rep(i,v.size()){if(i)cout<<' ';cout<<v[i];}cout<<'\n';}
const ll inf=1001001001001001001;
const ll mod=1000003;
int main(){
    ll n,ans=0;cin>>n;
    vi v(n);rep(i,n)cin>>v[i];
    vi srt=v;dupli(srt);
    vvi g(srt.size());
    rep(i,n)g[lb(srt,v[i])].pb(i);
    P rng(1,n-2);
    set<ll> idx;
    ll L=0,R=n-1;
    vi seg(n*2);
    rep(i,n)seg[i+n]=v[i];
    for(ll i=n-1;i>0;i--)seg[i]=min(seg[i*2],seg[i*2+1]);
    auto getmi(ll l,ll r){
        ll res=inf;
        for(l+=n,r+=n;l<r;l>>=1,r>>=1){
            if(l&1)chmin(res,seg[l++]);
            if(r&1)chmin(res,seg[--r]);
        }
        return res;
    };
    rep(i,srt.size()-1){
        ll x=srt[i],y=srt[i+1];
        while(rng.fi<=rng.se&&v[rng.fi-1]<=max(x,v[rng.fi])){
            idx.erase(rng.fi);
            chmax(v[rng.fi],x);
            rng.fi++;
        }
        while(rng.fi<=rng.se&&v[rng.se+1]<=max(x,v[rng.se])){
            idx.erase(rng.se);
            chmax(v[rng.se],x);
            rng.se--;
        }
        // cout<<x<<' '<<rng.fi<<' '<<rng.se<<endl;
        if(rng.fi>rng.se)break;
        for(ll j:g[i])if(rng.fi<=j&&j<=rng.se){
            idx.insert(j);
        }
        ll cnt=idx.size();
        if(cnt==0)continue;
        ll s1=(y-x)%mod,s2=(x+y-1)*(y-x)/2%mod;
        while(v[L]<=x)L++;
        while(v[R]<=x)R--;
        ll a=*idx.begin(),b;
        auto itr=idx.end();itr--;b=*itr;
        ll l=min(getmi(rng.fi,a),v[L]),r=min(getmi(b+1,rng.se+1),v[R]);
        // REP(j,rng.fi,a)chmin(l,v[j]);
        // REP(j,b+1,rng.se+1)chmin(r,v[j]);
        if(cnt==1){
            ans+=(l+r)*s1+s2;
            ans%=mod;
        }
        if(cnt>=2){
            ans+=(2*cnt-3+l+r+y)*s1+(2*cnt-3+cnt)*s2;
            ans%=mod;
        }
    }
    out(ans);
}

answer.code: In function ‘int main()’:
answer.code:35:26: error: a function-definition is not allowed here before ‘{’ token
   35 |     auto getmi(ll l,ll r){
      |                          ^
answer.code:67:18: error: ‘getmi’ was not declared in this scope
   67 |         ll l=min(getmi(rng.fi,a),v[L]),r=min(getmi(b+1,rng.se+1),v[R]);
      |                  ^~~~~
answer.code:71:21: error: ‘r’ was not declared in this scope
   71 |             ans+=(l+r)*s1+s2;
      |                     ^
answer.code:75:29: error: ‘r’ was not declared in this scope
   75 |             ans+=(2*cnt-3+l+r+y)*s1+(2*cnt-3+cnt)*s2;
      |                             ^