#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 Lmi(n,inf),Rmi(n,inf);
    {
        vi st;
        rep(i,n){
            while(st.size()&&st.back()>=v[i]){
                if(st.back()>v[i])chmin(Lmi[i],st.back());
                st.pop_back();
            }
            st.pb(v[i]);
        }
    }
    {
        vi st;
        for(int i=n-1;i>=0;i--){
            while(st.size()&&st.back()>=v[i]){
                if(st.back()>v[i])chmin(Rmi[i],st.back());
                st.pop_back();
            }
            st.pb(v[i]);
        }
    }
    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(Lmi[a],v[L]),r=min(Rmi[b],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);
}