#include <bits/stdc++.h>
using namespace std;
#define int long long
const int md = 1e6 + 3;
int n, a[5005], b[5005], pre[5005], suf[5005];
vector<pair<int, int>> v;
vector<pair<int, int>> op[5005];
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, 1e9);
pre[0] = 1e9; suf[n + 1] = 1e9;
int lo = 1e9, hi = 0;
while (j < n) {
vector<int> idx;
while (v[j].first == c) {
idx.push_back(v[j].second);
lo = min(lo, v[j].second);
hi = max(hi, v[j].second);
b[v[j].second] = c;
j++;
}
vector<int> bad;
for (int i = lo + 1; i < hi; i++) if (b[i] == 1e9)
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]);
if (bad.size() == 1) {
op[bad[0]].emplace_back(pre[bad[0]], suf[bad[0]]);
} else {
if (suf[bad[0]] < pre[bad.back()]) {
op[bad[0]].emplace_back(pre[bad[0]], suf[bad[0]]);
op[bad.back()].emplace_back(c, suf[bad.back()]);
} else {
op[bad[0]].emplace_back(pre[bad[0]], c);
op[bad.back()].emplace_back(pre[bad.back()], suf[bad.back()]);
}
for (size_t i = 1; i < bad.size() - 1; i++)
op[bad[i]].emplace_back(c, c);
}
}
c--;
}
int ans = 0;
for (int i = 1; i <= n; i++) {
reverse(op[i].begin(), op[i].end());
for (const auto p : op[i]) {
int amt = p.first + p.second + a[i];
ans = (ans + amt) % md;
a[i]++;
}
}
cout << ans;
}
