#include <bits/stdc++.h>
using namespace std;
#define int long long
const int md = 1e6 + 3;
int n, a[5005], b[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);
while (j < n) {
vector<int> idx;
while (v[j].first == c) {
idx.push_back(v[j].second);
b[v[j].second] = c;
j++;
}
if (idx.size() > 1) {
int s = idx.back(), e = idx[0];
for (int i = s + 1; i < e; i++)
if (b[i] == 1e9) op[i].emplace_back(c, c);
}
int acc = 1e9;
for (int i = 1; i < idx.back(); i++) {
if (acc != 1e9 && b[i] == 1e9) op[i].emplace_back(acc, c);
acc = min(acc, b[i]);
}
acc = 1e9;
for (int i = n; i > idx[0]; i--) {
if (acc != 1e9 && b[i] == 1e9) op[i].emplace_back(acc, c);
acc = min(acc, b[i]);
}
if (j >= n) break;
c = v[j].first;
}
int ans = 0;
for (int i = 1; i <= n; i++) {
reverse(op[i].begin(), op[i].end());
for (const auto p : op[i]) {
int m = min(p.first, p.second);
int d = m - a[i];
ans += d * (p.first + p.second);
ans += d * (a[i] + m) / 2;
ans %= md;
}
}
cout << ans;
}
