#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1'000'000 + 10,
M = 1'000'003,
MAX = 1'000'000'001;
int n;
int h[N];
int prefMax[N], suffMax[N];
int goalH[N];
int f[N << 2];
void build(int s, int l, int r) {
if (l == r) {
f[s] = h[l];
return;
}
int mid = (l + r) >> 1;
build(s << 1, l, mid); build(s << 1 | 1, mid + 1, r);
f[s] = min(f[s << 1], f[s << 1 | 1]);
}
void update(int s, int l, int r, int p, int x) {
if (p < l || p > r) return;
if (l == r) {
f[s] = x;
return;
}
int mid = (l + r) >> 1;
update(s << 1, l, mid, p, x); update(s << 1 | 1, mid + 1, r, p, x);
f[s] = min(f[s << 1], f[s << 1 | 1]);
}
int query(int s, int l, int r, int u, int v) {
if (v < l || u > r) return MAX;
if (u <= l && r <= v) return f[s];
int mid = (l + r) >> 1;
return min(query(s << 1, l, mid, u, v), query(s << 1 | 1, mid + 1, r, u, v));
}
set<int> s[N];
vector<int> del[N];
int32_t main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n;
for (int i = 1; i <= n; ++i) cin >> h[i];
build(1, 1, n);
vector<int> allValue(h + 1, h + n + 1);
sort(allValue.begin(), allValue.end());
allValue.erase(unique(allValue.begin(), allValue.end()), allValue.end());
for (int i = 1; i <= n; ++i)
h[i] = lower_bound(allValue.begin(), allValue.end(), h[i]) - allValue.begin();
for (int i = 1; i <= n; ++i) prefMax[i] = max(prefMax[i - 1], h[i]);
for (int i = n; i >= 1; --i) suffMax[i] = max(suffMax[i + 1], h[i]);
for (int i = 1; i <= n; ++i) goalH[i] = min(prefMax[i], suffMax[i]);
for (int i = 1; i <= n; ++i) {
s[h[i]].insert(i);
del[goalH[i]].push_back(i);
}
auto sum = [&](int l, int r) {
return (1ll * (r + l) * (r - l + 1) / 2) % M;
};
auto add = [&](auto& x, const auto& y) {
x += y;
if (x >= M) x -= M;
};
long long answer = 0;
set<int> vt;
for (int it = 0; it < (int)allValue.size() - 1; ++it) {
int height = allValue[it], nxtHeight = allValue[it + 1];
for (const auto& i : s[it]) {
vt.insert(i);
update(1, 1, n, i, MAX);
}
for (const auto& i : del[it]) vt.erase(i);
if (!vt.size()) continue;
int cnt = nxtHeight - height;
if (vt.size() == 1) {
int i = *vt.begin();
add(answer, 1ll * cnt * (query(1, 1, n, 1, i) + query(1, 1, n, i, n)) % M);
add(answer, sum(height, nxtHeight - 1));
} else {
int l = *vt.begin(), r = *vt.rbegin();
long long addLFirst = query(1, 1, n, 1, l) + query(1, 1, n, l, n) +
query(1, 1, n, r, n);
long long addRFirst = query(1, 1, n, 1, r) + query(1, 1, n, r, n) +
query(1, 1, n, 1, l);
add(answer, 1ll * min(addLFirst, addRFirst) % M * cnt % M);
add(answer, sum(height, nxtHeight - 1));
add(answer, sum(height, nxtHeight - 1));
add(answer, sum(height + 1, nxtHeight));
int total = 0;
add(total, sum(height, nxtHeight - 1));
add(total, sum(height + 1, nxtHeight));
add(total, sum(height + 1, nxtHeight));
add(answer, 1ll * (vt.size() - 2) % M * total % M);
}
}
cout << answer % M << "\n";
}
