#include <bits/stdc++.h>

using namespace std;
using ll = long long;

constexpr int MOD = 1e6 + 3;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    vector<int> h(n);

    for (int i = 0; i < n; ++i) {
        cin >> h[i];
    }

    ll best = 3e18;
    int p = max_element(h.begin(), h.end()) - h.begin();

    vector<int> need(h);

    for (int i = 1; i <= p; ++i) {
        need[i] = max(need[i], need[i - 1]);
    }
    for (int i = n - 2; i >= p; --i) {
        need[i] = max(need[i], need[i + 1]);
    }

    vector<set<int>> pos(h[p] + 1);
    vector<set<int>> alive(h[p] + 1);

    for (int i = 0; i < n; ++i) {
        pos[h[i]].insert(i);
        if (h[i] < need[i]) {
            alive[h[i]].insert(i);
        }
    }

    auto bestL = [&](int i) -> int {
        for (int k = h[i] + 1; k <= h[p]; ++k) {
            if (!pos[k].empty() && *pos[k].begin() < i) {
                return k;
            }
        }
        return 1e9;
    };

    auto bestR = [&](int i) -> int {
        for (int k = h[i] + 1; k <= h[p]; ++k) {
            if (!pos[k].empty() && *pos[k].rbegin() > i) {
                return k;
            }
        }
        return 1e9;
    };

    ll ans = 0;

    auto inc = [&](int a) {
        pos[h[a]].erase(a);
        alive[h[a]].erase(a);
        h[a] += 1;
        pos[h[a]].insert(a);
        if (h[a] < need[a]) {
            alive[h[a]].insert(a);
        }
    };

    while (true) {
        int a = -1, b = -1;
        for (int k = 0; k < size(alive); ++k) {
            if (!alive[k].empty()) {
                a = *alive[k].begin();
                b = *alive[k].rbegin();
                break;
            }
        }
        if (a == -1) {
            break;
        }
        if (a != b) {
            ll LA = bestL(a), RB = bestR(b);
            ll A = LA + bestR(a), B = bestL(b) + RB;
            ll costA = A + RB + h[a] + 1;
            ll costB = B + LA + h[b] + 1;
            if (costA > costB) {
                swap(a, b);
                swap(A, B);
                swap(LA, RB);
            }
            ans += A + h[a];
            ans += RB + h[a] + 1 + h[b];
            inc(a), inc(b);
        } else {
            ans += bestL(a) + bestR(a) + h[a];
            inc(a);
        }
    }

    best = min(best, ans);

    cout << best % MOD << '\n';

    return 0;
}