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

const int M = 1 << 20;

int c[M << 1];

inline void modify(int i, int v) {
    for(i += M; i; i >>= 1) c[i] = v, cmin(v, c[i ^ 1]);
}
inline int Pre(int i) {
    int res = inf;
    for(i += M; i > 1; i >>= 1)
        if(i & 1) cmin(res, c[i - 1]);
    return res;
}
inline int Suf(int i) {
    int res = inf;
    for(i += M; i > 1; i >>= 1)
        if(~i & 1) cmin(res, c[i + 1]);
    return res;
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n;
    mem(c, 63);
    rep(i, 1, n) cin >> h[i], modify(i, 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)) {
            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), modify(a, inf);
        else p.erase(-a);
        lst = now;
    }
    cout << ans << '\n';
}