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

    auto cost = [&](int i) -> int {
        if (need[i] == h[i]) {
            return -1e9;
        }
        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]);
            }
        }
        return l + r;
    };

    ll ans = 0;

    while (h != need) {
        int minH = numeric_limits<int>::max();
        for (int i = 0; i < n; ++i) {
            if (h[i] < need[i]) {
                minH = min(minH, h[i]);
            }
        }
        int a = -1, b = -1;
        for (int i = 0; i < n; ++i) {
            if (h[i] < need[i] && h[i] == minH) {
                b = i, a = (a == -1 ? i : a);
            }
        }
        ll A = cost(a);
        ll B = cost(b);
        h[a] += 1;
        ll costA = A + cost(b);
        h[a] -= 1;
        h[b] += 1;
        ll costB = B + cost(a);
        h[b] -= 1;
        if (costA > costB) {
            swap(a, b);
            swap(A, B);
        }
        ans += A + h[a];
        h[a] += 1;
    }

    best = min(best, ans);

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

    return 0;
}