#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) % mod + (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) % mod;
            assert(mnl >= new_val && mnr >= new_val);
            ll f = (int)st.size() - 1;
            rs = (rs + sum_on_seg(val + 1, new_val + 1) * (f + max(0ll, f - 1)) % mod) % mod;
            if (f > 1) {
                rs = (rs + new_val * (new_val - val)) % 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;
}