#include <bits/stdc++.h>

#define f first
#define s second
#define pb push_back
#define mp make_pair

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;

const int N = 1000500, inf = 1e9, mod = 1e6 + 3;
const ll INF = 1e18;

int sum(int a, int b) {
    a += b;
    if (a >= mod)
        a -= mod;
    return a;
}

int sub(int a, int b) {
    a -= b;
    if (a < 0)
        a += mod;
    return a;
}

int mult(int a, int b) {
    return 1ll * a * b % mod;
}

int bp(int a, int b) {
    int res = 1;
    while (b) {
        if (b & 1)
            res = mult(res, a);
        a = mult(a, a);
        b >>= 1;
    }
    return res;
}

int inv(int x) {
    return bp(x, mod - 2);
}

int n, a[N], p[N];
int ans;

int t[N << 2];

int get(int v, int tl, int tr, int l, int r) {
    if (r < tl || tr < l || l > r)
        return inf;
    if (l <= tl && tr <= r)
        return t[v];
    int tm = (tl + tr) >> 1;
    return min(get(v << 1, tl, tm, l, r), get(v << 1 | 1, tm + 1, tr, l, r));
}

void upd(int v, int tl, int tr, int p, int x) {
    if (tl == tr) {
        t[v] = x;
        return;
    }
    int tm = (tl + tr) >> 1;
    if (p <= tm)
        upd(v << 1, tl, tm, p, x);
    else
        upd(v << 1 | 1, tm + 1, tr, p, x);
    t[v] = min(t[v << 1], t[v << 1 | 1]);
}

void solve() {
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> a[i];


    int L = 0, R = n - 1;
    iota(p, p + n, 0);
    sort(p, p + n, [](int i, int j) {
        return a[i] < a[j];
    });

    set<int> st;

    for (int i = 0; i < n; i++)
        upd(1, 0, n - 1, i, a[i]);

    for (int i = 0, j = 0; i < n; i = j) {
        while (j < n && a[p[i]] == a[p[j]])
            j++;

        for (int q = i; q < j; q++)
            upd(1, 0, n - 1, p[q], inf);
        for (int q = i; q < j; q++)
            st.insert(p[q]);

        while (!st.empty() && *st.begin() == L) {
            st.erase(*st.begin());
            L++;
        }
        while (!st.empty() && *st.rbegin() == R) {
            st.erase(*st.rbegin());
            R--;
        }
        if (st.empty())
            continue;
        if (st.size() == 1) {
            int pos = *st.begin();
            ll x = get(1, 0, n - 1, 0, pos - 1) + get(1, 0, n - 1, pos + 1, n - 1);
            for (int q = a[p[i]]; q < a[p[j]]; q++)
                ans = (ans + x + q) % mod;
        } else {
            int l = *st.begin();
            int r = *st.rbegin();
            ll x = min(
                    get(1, 0, n - 1, 0, l - 1) + get(1, 0, n - 1, l + 1, n - 1) + get(1, 0, n - 1, r + 1, n - 1),
                    get(1, 0, n - 1, 0, r - 1) + get(1, 0, n - 1, r + 1, n - 1) + get(1, 0, n - 1, 0, l - 1)
            ) % mod;

            assert(st.size() >= 2);
            assert(a[p[i]] < a[p[j]]);

            ans = (ans + 1ll * x * (a[p[j]] - a[p[i]])) % mod;
            ans = (ans - 1ll * st.size() * (a[p[j]] - a[p[i]])) % mod;
            ll y = 1ll * (a[p[i]] + a[p[j]] + 1) * (a[p[j]] - a[p[i]]) / 2 % mod;
            ans = (ans + 3ll * (st.size() - 1) * y) % mod;
        }
    }
    if(ans < 0)
        ans += mod;
    cout << ans << "\n";
}

int main() {
#ifdef DEBUG
    freopen("input.txt", "r", stdin);
#endif
    ios_base::sync_with_stdio(false);
    int t = 1;
//    cin >> t;
    for (int i = 1; i <= t; i++) {
//        cout << "Case #" << i << endl;
        solve();
    }
}