#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 9;
const int mod = 1e6 + 3;
const int inf = 1e9 + 9;
//mod operator
int add(int x,int y) {
x += y;
if (x >= mod) x %= mod;
return x;
}
int mul(long long x,int y) {
x *= y;
if (x >= mod) x %= mod;
return x;
}
int subtract(int x,int y) {
return add(x,mod - y);
}
int power(int x,int y) {
if (y == 0) return 1;
if (y % 2 == 0) {
int a = power(x,y / 2);
return mul(a,a);
} else {
int a = power(x,y - 1);
return mul(a,x);
}
}
#define re exit(0);
int n,h[maxn],desire[maxn],maxheight;
struct ev {
int height,pos,val;
} event[maxn * 2];
int st[maxn * 4];
void build(int id,int l,int r) {
if (l == r) {
st[id] = h[l];
return;
}
int mid = (l + r) >> 1;
build(id*2,l,mid);
build(id*2+1,mid+1,r);
st[id] = min(st[id*2],st[id*2+1]);
}
void update(int id,int l,int r,int pos,int val) {
if (l > pos || r < pos) return;
if (l == r) {
st[id] = val;
return;
}
int mid = (l + r) >> 1;
update(id*2,l,mid,pos,val);
update(id*2+1,mid+1,r,pos,val);
st[id] = min(st[id*2],st[id*2+1]);
}
int get(int id,int l,int r,int u,int v) {
if (l > v || r < u) return inf;
if (l >= u && r <= v) return st[id];
int mid = (l + r) >> 1;
return min(get(id*2,l,mid,u,v),get(id*2+1,mid+1,r,u,v));
}
set <int> online;
long long sum(int l,int r) {
return 1ll*(r + l)*(r - l + 1)/2;
}
int main() {
ios_base::sync_with_stdio(0);cin.tie(nullptr);
// freopen(".inp","r",stdin);
// freopen(".out","w",stdout);
cin >> n;
for (int i = 1;i <= n;i++) cin >> h[i];
maxheight = *max_element(h + 1,h + 1 + n);
int pt;
for (pt = 1;pt <= n;pt++) {
if (h[pt] == maxheight) break;
desire[pt] = max(desire[pt - 1],h[pt]);
}
int pt2;
for (pt2 = n;pt2 >= 1;pt2--) {
if (h[pt2] == maxheight) break;
desire[pt2] = max(desire[pt2 + 1],h[pt2]);
}
for (int i = pt;i <= pt2;i++) desire[i] = maxheight;
for (int i = 1;i <= n;i++) {
event[i] = {h[i],i,1};
event[i + n] = {desire[i],i,-1};
}
sort(event + 1,event + 1 + 2*n,[] (ev a,ev b) {
if (a.height != b.height) return a.height < b.height;
return a.val > b.val;
});
build(1,1,n);
int res = 0;
for (int i = 1;i <= 2*n;i++) {
int d = event[i].height;
if (event[i].val == 1) {
online.insert(event[i].pos);
update(1,1,n,event[i].pos,inf);
}
else online.erase(event[i].pos);
while (i < 2 * n && event[i + 1].height == d) {
i++;
if (event[i].val == 1) {
online.insert(event[i].pos);
update(1,1,n,event[i].pos,inf);
}
else online.erase(event[i].pos);
}
if (i == 2 * n) break;
if (online.empty()) continue;
int l = *online.begin(),r = *online.rbegin();
int aim = event[i + 1].height,curr = d;
long long FUCK = sum(curr,aim - 1);
if (online.size() == 1) {
int d1 = get(1,1,n,1,l - 1),d2 = get(1,1,n,r + 1,n);
res = add(res,add( mul(add(d1,d2),aim - curr),FUCK%mod ));
continue;
}
int fuckleft = get(1,1,n,1,l - 1),fuckright = get(1,1,n,r + 1,n);
int fuckmid = get(1,1,n,l + 1,r - 1);
//default cost
res = add(res, mul(online.size() - 2 , add( mul(3,FUCK%mod) , mul(2,aim - curr) ) ) );
//min raise left and right
long long costleft = 2*FUCK + 1ll*(aim - curr)*(fuckleft + min(fuckmid,fuckright)) + sum(curr + 1,aim) + 1ll*(aim - curr)*fuckright;
long long costright = 2*FUCK + 1ll*(aim - curr)*(min(fuckleft,fuckmid) + fuckright) + sum(curr + 1,aim) + 1ll*(aim - curr)*fuckleft;
res = add(res,min(costleft,costright)%mod);
}
cout << res;
}
