#include <bits/stdc++.h>


using namespace std;

#define int long long
#define ll long long
#define flt double
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()


mt19937 rnd(234);
const ll mod = 1e6 + 3;
const ll inf = 1e18;


struct SGT{
    int n;
    vector<ll> t;
    
    void build(vector<ll> &a){
        n = 1;
        while(n < (int)a.size()){
            n *= 2;
        }
        t.assign(n + n, 0);
        for(int i = 0; i < (int)a.size(); i += 1){
            t[i + n] = a[i];
        }
        for(int i = n - 1; i >= 1; i -= 1){
            t[i] = min(t[i + i], t[i + i + 1]);
        }
    }


    ll get(int l, int r){
        l += n;
        r += n;
        ll rs = inf;
        while(l < r){
            if(l & 1){
                rs = min(rs, t[l]);
                l += 1;
            }
            if(r & 1){
                r -= 1;
                rs = min(rs, t[r]);
            }
            l /= 2;
            r /= 2;
        }
        return rs;
    }
};



ll sum_on_seg(ll l, ll r){
    return (l * (r - l) + (r - l - 1) * (r - l) / 2) % mod;
}


int n;
vector<ll> h;


ll solve(){
    ll rs = 0;
    vector<pair<ll, int>> srtd(n);
    for(int i = 0; i < n; i += 1){
        srtd[i] = make_pair(h[i], i);
    }
    sort(all(srtd));
    int i = 0;
    int l = 0;
    int r = n - 1;
    set<int> st;
    ll val = -inf;
    SGT sgt;
    sgt.build(h);
    while(l < r){
        ll new_val = val;
        if(i < n){
            new_val = srtd[i].first;
        }
        if(!st.empty()){
            int x = *st.begin();
            int y = *prev(st.end());
            ll mnl = sgt.get(l, x);
            ll mnr = sgt.get(y + 1, r + 1);
            rs = (rs + (mnl + mnr) * (new_val - val)) % mod;
            ll f = (int)st.size() - 1;
            rs = (rs + sum_on_seg(val + 1, new_val + 1) * f) % mod;
        }
        val = new_val;
        while(i < n && srtd[i].first == val){
            st.insert(srtd[i].second);
            i += 1;
        }
        while(!st.empty() && l == *st.begin()){
            st.erase(st.begin());
            rs = (rs + sum_on_seg(h[l], val)) % mod;
            l += 1;
        }
        while(!st.empty() && r == *prev(st.end())){
            st.erase(prev(st.end()));
            rs = (rs + sum_on_seg(h[r], val)) % mod;
            r -= 1;
        }
    }
    return rs;
}


int32_t main(){
    if(1){
        ios::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
    }
    cin >> n;
    h.resize(n);
    for(int i = 0; i < n; i += 1){
        cin >> h[i];
    }
    cout << solve() << "\n";
    return 0;
}