#include <bits/stdc++.h>

using namespace std;
using i64 = long long;

#define rep(i, l, r) for (int i = (l); i < (r); ++i)
#define per(i, l, r) for (int i = (r - 1); i >= (l); --i)
#define ALL(x) (x).begin(), (x).end()

struct SegTree {
    int n, s;
    vector<i64> data;

    void update(int i) {
        data[i] = min(data[2 * i], data[2 * i + 1]);
    }

    SegTree(int n) : n(n) {
        s = 1;
        while (s < n) s *= 2;
        data.assign(2 * s, (1ll << 60));
    }

    void set(int p, i64 v) {
        p += s;
        data[p] = v;
        while (p != 1) {
            update(p /= 2);
        }
    }

    i64 fold(int l, int r) {
        i64 ret = 1ll << 60;
        l += s, r += s;
        while (l < r) {
            if (l & 1) ret = min(ret, data[l++]);
            if (r & 1) ret = min(data[--r], ret);
            l /= 2;
            r /= 2;
        }
        return ret;
    }
};

constexpr i64 mod = 1000003;

int main() {
    int N;
    cin >> N;
    vector<i64> H(N);
    for (auto &e : H) cin >> e;
    auto vs = H;
    sort(ALL(vs));
    vs.erase(unique(ALL(vs)), vs.end());

    assert(N <= 5000);
    vector<i64> lMax(N + 1), rMax(N + 1);
    rep (i, 0, N) lMax[i + 1] = max(lMax[i], H[i]);
    per (i, 0, N) rMax[i] = max(rMax[i + 1], H[i]);

    int p = (int)(std::max_element(H.begin(), H.end()) - H.begin());

    vector<i64> lma(N + 1), rma(N + 1);
    rep (i, 0, N) lma[i + 1] = max(lma[i], H[i]);
    per (i, 0, N) rma[i] = max(rma[i + 1], H[i]);
    vector<i64> res(N);
    rep (i, 0, p) res[i] = lma[i + 1];
    res[p] = H[p];
    rep (i, p + 1, N) res[i] = rma[i];

    i64 ans = 0;
    rep (i, 0, N) {
        const auto s = res[i] - H[i];
        ans += s * (2 * H[i] + s - 1) / 2;
        ans %= mod;
    }

    vector<vector<int>> addList(vs.size()), delList(vs.size());
    rep (i, 0, N) {
        auto l = (int)(lower_bound(ALL(vs), H[i]) - vs.begin());
        auto r = (int)(lower_bound(ALL(vs), res[i]) - vs.begin());
        addList[l].push_back(i);
        delList[r].push_back(i);
    }

    SegTree seg(N);
    rep (i, 0, N) seg.set(i, H[i]);

    set<int> ids;
    rep (i, 0, (int)vs.size()) {
        i64 w = vs[i] - (i == 0 ? 0 : vs[i - 1]);
        if (not ids.empty()) {
            const auto llv = seg.fold(0, *ids.begin());
            const auto rrv = seg.fold(*ids.rbegin(), 0);
            const auto lrv = seg.fold(*ids.begin(), N);
            const auto rlv = seg.fold(0, *ids.rbegin());
            if (ids.size() == 1) {
                ans += w * (llv + lrv);
            } else {
                ans += w * (llv + rrv + std::min(lrv, rlv));
                const auto s = 2 * ids.size() - 3;
                ans += ((vs[i] + 1) + (vs[i] + w)) * w / 2 % mod * s;
            }
            ans %= mod;
        }

        for (const auto e : addList[i]) {
            ids.insert(e);
            seg.set(e, 1ll << 60);
        }
        for (const auto e : delList[i]) ids.erase(e);
    }

    cout << ans << endl;
}