#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);
    map<int, vector<int>> evt;
    rep(i, 1, n) evt[h[i]].pb(i), evt[tar[i]].pb(-i);
    int lst = 0, ans = 0;
    set<int> p;
    for(auto [now, e] : evt) {
        if(SZ(p)) {
            static int pre[N], suf[N];
            pre[0] = suf[n + 1] = inf;
            rep(i, 1, n) pre[i] = min(pre[i - 1], h[i]);
            per(i, n, 1) suf[i] = min(suf[i + 1], h[i]);
            int L = *p.begin(), R = *p.rbegin();
            ll cnt = now - lst, sum = ((lst + now - 1) * cnt >> 1) % P;
            ans = (ans + sum * SZ(p)) % P;
            ans = (ans + cnt * (pre[L] + suf[R])) % P;
            if(SZ(p) > 1) {
                ans = (ans + (sum + cnt) * (SZ(p) * 2 - 3)) % P;
                ans = (ans + cnt * min(suf[L], pre[R])) % P;
            }
        }
        for(int a : e) if(a > 0) p.insert(a), h[a] = inf;
        else p.erase(-a);
        lst = now;
    }
    cout << ans << '\n';
}