#include <bits/stdc++.h>
using namespace std;
#define int long long
const int md = 1e6 + 3;
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[1000005], b[1000005];
vector<pair<int, int>> v;
set<int> st;
int t[2048576];
void update(int p, int v) {
for (t[p += n] = v; p > 1; p >>= 1) t[p >> 1] = min(t[p], t[p ^ 1]);
}
int query(int l, int r) {
int res = 1e18;
for (l += n, r += n + 1; l < r; l >>= 1, r >>= 1) {
if (l & 1) res = min(res, t[l++]);
if (r & 1) res = min(res, t[--r]);
}
return res;
}
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, 1e18);
fill(t, t + 2048576, 1e18);
int ans = 0, prev = c;
int lo = 1e18, hi = -1, inv2 = 500002;
while (j < n) {
vector<int> idx;
while (v[j].first == c) {
idx.push_back(v[j].second);
j++;
}
if (!st.empty()) {
int fi = *st.begin(), la = *st.rbegin();
int diff = (prev - c) % md;
if (st.size() == 1) {
int cont = (query(1, fi) + query(fi, n)) % md;
ans = (ans + modMul(cont, diff)) % md;
int temp = modMul(modMul((c + prev - 1) % md, diff), inv2);
ans = (ans + temp) % md;
} else {
int cont = (query(1, fi) + query(la, n) + 2 * (int) st.size() - 3) % md;
int t1 = query(fi, n), t2 = query(1, la);
if (t1 < t2) cont = (cont + t1) % md;
else cont = (cont + t2) % md;
ans = (ans + modMul(cont, diff)) % md;
int f = (3 * (int) st.size() - 3) % md;
int temp = modMul(modMul(modMul((c + prev - 1) % md, diff), inv2), f);
ans = (ans + temp) % md;
}
}
int nlo = lo, nhi = hi;
for (const int u : idx) {
b[u] = c;
update(u, c);
st.erase(u);
nlo = min(u, nlo);
nhi = max(u, nhi);
}
if (hi != -1) {
for (int i = hi + 1; i < nhi; i++) if (b[i] == 1e18) st.insert(i);
for (int i = nlo + 1; i < lo; i++) if (b[i] == 1e18) st.insert(i);
} else {
for (int i = nlo + 1; i < nhi; i++) if (b[i] == 1e18) st.insert(i);
}
lo = nlo, hi = nhi;
if (j >= n) break;
prev = c;
c = v[j].first;
}
cout << ans;
}
