//我好笨，聽解了
/*
x +
*/
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int M = 1e6 + 3, N = M + 20, INF = (INT_MAX >> 1) - 3;
int o[N], n;
vector <int> v[N], b;
struct segmenttree {
int a[N << 2];
void build (int l, int r, int id) {
if (l == r) {
a[id] = b[o[l]];
return;
}
int mid = (l + r) >> 1;
build (l, mid, id << 1); build (mid + 1, r, id << 1 | 1);
a[id] = min(a[id << 1], a[id << 1 | 1]);
}
int query (int l, int r, int ql, int qr, int id) {
if (ql < 1 or qr > n or ql > qr) return INF;
if (ql <= l and r <= qr) return a[id];
int mid = (l + r) >> 1, ans = INT_MAX;
if (ql <= mid) ans = min(ans, query(l, mid, ql, qr, id << 1));
if (qr > mid) ans = min(ans, query(mid + 1, r, ql, qr, id << 1 | 1));
return ans;
}
void update (int l, int r, int pos, int val, int id) {
if (l == r) {
a[id] = o[pos] = val;
return;
}
int mid = (l + r) >> 1;
if (pos <= mid) update(l, mid, pos, val, id << 1);
else update(mid + 1, r, pos, val, id << 1 | 1);
a[id] = min(a[id << 1], a[id << 1 | 1]);
}
}seg;
inline int f (int l, int r) {
return (r - l + 1LL) * (r + l) / 2 % M;
}
int main () {
ios_base::sync_with_stdio(false); cin.tie(0);
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> o[i];
b.push_back(o[i]);
}
sort(b.begin(), b.end());
b.erase(unique(b.begin(), b.end()), b.end());
for (int i = 1; i <= n; i++) {
o[i] = lower_bound(b.begin(), b.end(), o[i]) - b.begin();
v[o[i]].push_back(i);
}
seg.build(1, n, 1);
set<int> st;
ll ans = 0;
for (int h = 0; h + 1 < b.size(); h++) {
int oh = b[h], nh = b[h + 1];
for (int x : v[h]) {
st.insert(x);
seg.update(1, n, x, INF, 1);
}
while (st.size()) {
int i = *st.begin();
int left = seg.query(1, n, 1, i - 1, 1), right = seg.query(1, n, i + 1, n, 1);
if (left == INF or right == INF) st.erase(i);
else break;
}
while (st.size()) {
int i = *st.rbegin();
int left = seg.query(1, n, 1, i - 1, 1), right = seg.query(1, n, i + 1, n, 1);
if (left == INF or right == INF) st.erase(i);
else break;
}
if (st.size() == 1) {
int i = *st.begin();
int left = seg.query(1, n, 1, i - 1, 1), right = seg.query(1, n, i + 1, n, 1);
ans += f(oh, nh - 1) + (left +right) * 1LL * (nh - oh) % M;
}
else if (st.size() >= 2) {
int il = *st.begin(), ir = *st.rbegin();
ll left = seg.query(1, n, 1, il - 1, 1), right = seg.query(1, n, ir + 1, n, 1);
ll mid = seg.query(1, n, il + 1, ir - 1, 1);
ll z = min( (left + right + min(left, right)) * 1LL * (nh - oh) + f(oh + 1, nh) + f(oh, nh - 1) * 2 ,
(left + mid + right) * 1LL * (nh - oh) + f(oh + 1, nh) + f(oh, nh - 1) * 2 );
ans += z % M;
ans += (st.size() - 2) * (f(oh + 1, nh) * 2LL + f(oh, nh - 1)) % M;
}
ans %= M;
}
cout << ans << '\n';
return 0;}
