#include <bits/stdc++.h>
#define rep(i, l, r) for(int i = (l); i <= (r); i++)
#define per(i, r, l) for(int i = (r); i >= (l); i--)
#define mem(a, b) memset(a, b, sizeof a)
#define For(i, l, r) for(int i = (l), i##e = (r); i < i##e; i++)
#define pb push_back
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define SZ(x) int((x).size())

using namespace std;
using ll = long long;

template<class T> inline T& cmin(T& a, const T& b) { if(b < a) a = b; return a; }
template<class T> inline T& cmax(T& a, const T& b) { if(a < b) a = b; return a; }
template<class... Args> void print(Args&&... args) {
    ((cout << args << ' '), ...);
}
template<class... Args> void println(Args&&... args) {
    print(args...), cout << endl;
}

const int N = 5000 + 8, inf = 0x3f3f3f3f, P = 1e6 + 3;

int n, h[N], tar[N];

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n;
    rep(i, 1, n) cin >> h[i];
    int mx = 0;
    rep(i, 1, n) cmax(mx, h[i]), tar[i] = mx;
    mx = 0;
    per(i, n, 1) cmax(mx, h[i]), cmin(tar[i], mx);
    ll ans = 0;
    rep(v, 1, 99) {
        vector<int> p;
        rep(i, 1, n) if(h[i] == v & tar[i] != v) p.pb(i);
        if(p.empty()) continue;
        static int pre[N], suf[N];
        pre[0] = suf[n + 1] = inf;
        rep(i, 1, n) pre[i] = min(pre[i - 1], h[i] > v ? h[i] : inf);
        per(i, n, 1) suf[i] = min(suf[i + 1], h[i] > v ? h[i] : inf);
        ans += p.size() * v + pre[p[0]] + suf[p.back()];
        if(SZ(p) > 1)
            ans += min(suf[p[0]], pre[p.back()]) + (v + 1) * (p.size() * 2 - 3);
        for(int i : p) h[i]++;
    }
    cout << ans % P << '\n';
}