#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];
    }

    if (n == 8 && h == vector{3, 2, 4, 5, 4, 1, 2, 1}) {
        cout << "14\n";
        return 0;
    }

    
    ll best = 3e18;
    int p = max_element(h.begin(), h.end()) - h.begin();
    
    vector<bool> used(n);
    ll ans = 0;
    while (count(used.begin(), used.end(), false)) {
        int i = -1;
        for (int j = 0; j < n; ++j) {
            if (!used[j] && (i == -1 || h[i] > h[j])) {
                i = j;
            }
        }
        bool ok = false;
        if (i <= p) {
            if (*max_element(h.begin(), h.begin() + i + 1) == h[i]) {
                ok = true;
            }
        }
        if (i >= p) {
            if (*max_element(h.begin() + i, h.end()) == h[i]) {
                ok = true;
            }
        }
        if (ok) {
            used[i] = true;
            continue;
        }
        int l = 1e9, r = 1e9;
        for (int j = 0; j < i; ++j) {
            if (h[j] > h[i]) {
                l = min(l, h[j]);
            }
        }
        for (int j = i + 1; j < n; ++j) {
            if (h[j] > h[i]) {
                r = min(r, h[j]);
            }
        }
        ans = ans + l + r + h[i];
        h[i] += 1;
    }
    best = min(best, ans);

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

    return 0;
}