#include <bits/stdc++.h>
using namespace std;
using pii = pair<int,int>;
#define fs first
#define sc second
int n, a[20100], o[5100];
int main () {
ios_base::sync_with_stdio(false); cin.tie(0);
set<pii>st;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> o[i];
st.insert({o[i], i});
}
long long ans = 0;
int target = min(o[1], o[n]);
for (int h = 1; h <= 100; h++) {
if (h > target) break;
int ll[5010], rr[5010];
ll[0] = rr[n + 1] = INT_MAX;
for (int i = 1; i <= n; i++) {
ll[i] = ll[i - 1];
if (o[i] == h - 1) continue;
ll[i] = min(ll[i - 1], o[i]);
}
for (int i = n; i >= 1; i--) {
rr[i] = rr[i + 1];
if (o[i] == h - 1) continue;
rr[i] = min(rr[i + 1], o[i]);
}
vector <int> v;
for (int i = 1; i <= n; i++) if (o[i] == h - 1) v.push_back(i);
if (v.size() == 0) continue;
if (v.size() == 1) {
int i = v[0];
ans += ll[i - 1] * (h - 1) * rr[i + 1];
o[i] = h;
continue;}
int z = min(ll[v[0] - 1] * (h - 1) * rr[v[0] + 1] + h * (h - 1) * rr[v.back() + 1],
ll[v.back() - 1] * (h - 1) * rr[v.back() + 1] + ll[v[0] - 1] * (h - 1) * h);
z += (v.size() - 2) * (h - 1) * 1LL * h * h;
ans += z;
// cout << ll[v[0] - 1] * (h - 1) * rr[v[0] + 1] + h * (h - 1) * rr[v.back() + 1] << ' ' <<
// ll[v.back() - 1] * (h - 1) * rr[v.back() + 1] + ll[v[0] - 1] * (h - 1) * h << " ";
// cout << h << ' ' << z << '\n';
for (int x : v) o[x] = h;
}
cout << ans % (1000000 + 3) << '\n';
}
