#include <bits/stdc++.h>

using namespace std;

constexpr int N = 1e6 + 5, inf = 1e9, P = 1e6 + 3;

int a[N], pre[N], suf[N], Pre[N], Suf[N];

signed main() {
    int n; scanf("%d", &n);
    for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
    map<int, vector<int> > opt;
    for (int i = 1; i <= n; ++i) pre[i] = max(pre[i - 1], a[i]);
    for (int i = n; i >= 1; --i) suf[i] = max(suf[i + 1], a[i]);
    
    vector<int> a_disk(a + 1, a + n + 1);
    ranges::sort(a_disk);
    auto rng = ranges::unique(a_disk);
    a_disk.erase(rng.begin(), rng.end());
    auto getId = [&](int x) {
        return ranges::lower_bound(a_disk, x) - a_disk.begin() + 1;
    };

    static int mn[N];
    fill(mn + 1, mn + a_disk.size() + 1, inf);
    
    auto query = [&](int x) {
        int res = inf;
        for (; x <= (int)a_disk.size(); x += x & -x) res = min(res, mn[x]);
        return res;
    };

    auto modify = [&](int x, int y) {
        for (; x; x -= x & -x) mn[x] = min(mn[x], y);
    };

    for (int i = 1; i <= n; ++i) {
        int ind = getId(a[i]);
        Pre[i] = query(ind + 1);
        modify(ind, a[i]);
    }
    fill(mn + 1, mn + a_disk.size() + 1, inf);
    for (int i = n; i >= 1; --i) {
        int ind = getId(a[i]);
        Suf[i] = query(ind + 1);
        modify(ind, a[i]);
    }

    auto Sum = [&](int l, int r) -> int {
        return 1ll * (l + r) * (r - l + 1) / 2 % P;
    };

    int res = 0;
    for (int i = 1; i <= n; ++i) {
        opt[a[i]].push_back(i);
        opt[min(pre[i], suf[i])].push_back(-i);
        res = (res + Sum(a[i], min(pre[i], suf[i]) - 1)) % P;
    }

    set<int> S;
    for (auto [x, y] : opt) {
        if (opt.upper_bound(x) == opt.end()) break;
        int nxt = opt.upper_bound(x) -> first;
        for (auto z : y) {
            if (z > 0) S.insert(z);
            else S.erase(S.find(-z));
        }
        if (S.empty()) continue;
        if (S.size() == 1) {
            res = (res + 1ll * (Pre[*S.begin()] + Suf[*S.begin()]) * (nxt - x)) % P;
        } else {
            res = (res + (2ll * S.size() - 3) * Sum(x, nxt - 1) + (0ll + Pre[*S.begin()] + Suf[*S.rbegin()] + min(Suf[*S.begin()], Pre[*S.rbegin()])) * (nxt - x)) % P;
        }
    }

    printf("%d\n", res);
    return 0;
}