#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,popcnt,sse4,abm")
#include <bits/stdc++.h>
using namespace std;
#ifdef WAIMAI
#define debug(HEHE...) cout << "[" << #HEHE << "] : ", dout(HEHE)
void dout() {cout << '\n';}
template<typename T, typename...U>
void dout(T t, U...u) {cout << t << (sizeof...(u) ? ", " : ""), dout(u...);}
#else
#define debug(...) 7122
#endif
#define ll long long
#define Waimai ios::sync_with_stdio(false), cin.tie(0)
#define FOR(x,a,b) for (int x = a, I = b; x <= I; x++)
#define pb emplace_back
#define F first
#define S second
#define lpos pos*2
#define rpos pos*2+1
const int INF = 2e9;
const int MOD = 1e6 + 3;
const int SIZE = 1e6 + 5;
int n, mx;
ll ans;
int a[SIZE];
pair<int, int> val[SIZE];
ll sum(int l, int r) {
return 1ll * (r - l + 1) * (l + r) / 2 % MOD;
}
int mn[SIZE << 2];
void build(int pos, int l, int r) {
if (l == r) {
mn[pos] = a[l];
return;
}
int mid = (l + r) / 2;
build(lpos, l, mid);
build(rpos, mid + 1, r);
mn[pos] = min(mn[lpos], mn[rpos]);
}
void upd(int pos, int l, int r, int p) {
if (l == r) {
mn[pos] = INF;
return;
}
int mid = (l + r) / 2;
if (p <= mid) upd(lpos, l, mid, p);
else upd(rpos, mid + 1, r, p);
mn[pos] = min(mn[lpos], mn[rpos]);
}
int que(int pos, int l, int r, int L, int R) {
if (l == L && r == R) return mn[pos];
int mid = (L + R) / 2;
if (r <= mid) return que(lpos, l, r, L, mid);
if (l > mid) return que(rpos, l, r, mid + 1, R);
return min(que(lpos, l, mid, L, mid), que(rpos, mid + 1, r, mid + 1, R));
}
set<int> s;
void solve() {
cin >> n;
FOR (i, 1, n) cin >> a[i], val[i] = {a[i], i};
sort(val + 1, val + n + 1);
build(1, 1, n);
FOR (vi, 1, n - 1) {
s.insert(val[vi].S);
upd(1, 1, n, val[vi].S);
if (val[vi].F == val[vi + 1].F) continue;
int x = val[vi].F, y = val[vi + 1].F - 1, len = y - x + 1;
int lmn = 0, rmn = 0, lv = 0, rv = 0;
while (s.size()) {
int i = *s.begin(), mn = INF;
if (i > 1) mn = que(1, 1, i - 1, 1, n);
if (mn == INF) {
s.erase(s.begin());
continue;
}
lmn = mn;
break;
}
while (s.size()) {
int i = *prev(s.end()), mn = INF;
if (i < n) mn = que(1, i + 1, n, 1, n);
if (mn == INF) {
s.erase(prev(s.end()));
continue;
}
rmn = mn;
break;
}
if (s.size() == 0) continue;
lv = que(1, *s.begin() + 1, n, 1, n);
rv = que(1, 1, *prev(s.end()) - 1, 1, n);
if (s.size() == 1) ans += 1ll * len * (lmn + rmn) + sum(x, y);
else ans += 1ll * len * ((ll) lmn + min(lv, rv) + rmn + 1) % MOD + 3 * sum(x, y) + 1ll * (s.size() - 2) * (3 * sum(x, y) + 2 * len) % MOD;
ans %= MOD;
}
cout << ans << '\n';
}
int main() {
Waimai;
solve();
}
