#include <bits/stdc++.h>
using namespace std;
#define int long long
const int md = 1e6 + 3;
int modexp(int base, int exp, int mod) {
int res = 1;
base %= mod;
while(exp) {
if(exp & 1)
res = (res * base) % mod;
base = (base * base) % mod;
exp /= 2;
}
return res;
}
int modinv(int a, int mod) {
return modexp(a, mod - 2, mod);
}
int modMul(int a, int b) {
return ((a % md) * (b % md)) % md;
}
int modAdd(int a, int b) {
return ((a % md) + (b % md)) % md;
}
int n, a[5005], b[5005], pre[5005], suf[5005];
vector<pair<int, int>> v;
int32_t main() {
ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
cin >> n; for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i <= n; i++) v.emplace_back(a[i], i);
sort(v.begin(), v.end(), greater<pair<int, int>>());
int j = 0, c = v[0].first;
fill(b, b + n + 1, 2e9);
int ans = 0, prev = c;
pre[0] = 2e9; suf[n + 1] = 2e9;
int lo = 2e9, hi = 0, inv2 = modinv(2, md);
while (j < n) {
vector<int> idx;
while (v[j].first == c) {
idx.push_back(v[j].second);
j++;
}
vector<int> bad;
for (int i = lo + 1; i < hi; i++) if (b[i] == 2e9)
bad.push_back(i);
if (!bad.empty()) {
for (int i = 1; i <= n; i++) pre[i] = min(pre[i - 1], b[i]);
for (int i = n; i >= 1; i--) suf[i] = min(suf[i + 1], b[i]);
int diff = (prev - c) % md;
if (bad.size() == 1) {
int cont = (pre[bad[0]] + suf[bad[0]]) % md;
ans = (ans + modMul(cont, diff)) % md;
int temp = modMul(modMul((c + prev - 1) % md, diff), inv2);
ans = (ans + temp) % md;
} else {
int cont = (pre[bad[0]] + suf[bad.back()] + 2 * (int)bad.size() - 3) % md;
if (suf[bad[0]] < pre[bad.back()])
cont = (cont + suf[bad[0]]) % md;
else
cont = (cont + pre[bad.back()]) % md;
ans = (ans + modMul(cont, diff)) % md;
int f = (3 * (int)bad.size() - 3) % md;
int temp = modMul(modMul(modMul((c + prev - 1) % md, diff), inv2), f);
ans = (ans + temp) % md;
}
}
for (const int u : idx) {
b[u] = c;
lo = min(u, lo);
hi = max(u, hi);
}
if (j >= n) break;
prev = c;
c = v[j].first;
}
cout << ans;
}
