#include<bits/stdc++.h>
#define fori(i,a,b) for(int i = a;i <= b; i++)
#define int long long
#define pb push_back
using namespace std;
typedef pair<int,int> ii;
typedef tuple<int,int,int> tp;
const int M = 1e6 + 10;
const int N = 5e3 + 10;
const int mod = 1e6 + 3;
int n,h[M];
int target[M];
vector<int> in[M],out[M];
vector<int> rrh;
int calc(int l,int r) {
return ((l + r) * (r - l + 1) / 2) % mod;
}
int t[4 * M];
void build(int s,int l, int r)
{
if(l == r) {
t[s] = h[l];
return ;
}
int mid = (l + r)/2;
build(s * 2,l,mid);
build(s * 2 + 1, mid + 1, r);
t[s] = min(t[s * 2] , t[s * 2 + 1]);
}
void upd(int s,int l, int r, int pos, int val)
{
if(l > pos || pos > r) return ;
if(l == r) {
t[s] = val;
return ;
}
int mid = (l + r)/2;
upd(s * 2, l, mid, pos, val);
upd(s * 2 + 1, mid + 1, r, pos, val);
t[s] = min(t[s * 2],t[s * 2 + 1]);
}
int get(int s, int l, int r, int u, int v)
{
if(l > v || r < u) return 1e9;
if(u <= l && r <= v) return t[s];
int mid = (l + r)/2;
return min(get(s * 2, l, mid, u, v),get(s * 2 + 1, mid + 1, r, u, v));
}
int32_t main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
if(fopen("1.inp","r"))
{
freopen("1.inp","r",stdin);
freopen("1.out","w",stdout);
}
#define task ""
if(fopen(task".inp","r"))
{
freopen(task".inp","r",stdin);
freopen(task".out","w",stdout);
}
cin >> n;
for(int i = 1;i <= n; i++) cin >> h[i];
build(1,1,n);
int suf = 0,pre = 0;
for(int i = 1;i <= n; i++) {
pre = max(pre, h[i]);
target[i] = pre ;
}
for(int i = n; i != 0; i--) {
suf = max(suf, h[i]);
target[i] = min(target[i], suf);
}
for(int i = 1;i <= n; i++) rrh.pb(h[i]);
sort(rrh.begin(),rrh.end());
rrh.resize(unique (rrh.begin(), rrh.end()) - rrh.begin());
for(int i = 1;i <= n; i++) {
h[i] = lower_bound(rrh.begin(),rrh.end(),h[i]) - rrh.begin() ;
target[i] = lower_bound(rrh.begin(),rrh.end(),target[i]) - rrh.begin() ;
if(h[i] != target[i]) {
out[target[i]].pb(i);
}
in[h[i]].pb(i);
}
int kq = 0;
int m= rrh.size();
set<int> s;
for(int high = 0;high <= m - 2; high ++) {
for(int idx : in[high]) {
if(h[idx] != target[idx]) s.insert(idx);
upd(1,1,n,idx,1e9);
}
int sz = s.size();
if(sz == 0) continue;
int val = rrh[high] % mod;
int nxt_val = rrh[high + 1] % mod;
if(sz == 1) {
int cur = *s.begin();
int x = get(1, 1, n, 1, cur - 1) , y = get(1, 1, n, cur + 1, n);
x %= mod;
y %= mod;
kq = (kq + (nxt_val - val)*(x + y) % mod ) % mod;
}
else {
int l = *s.begin(), r = *s.rbegin();
int pre_l = get(1, 1, n, 1, l - 1) , pre_r = get(1, 1, n, 1, r - 1) ,
suf_l = get(1, 1, n, l + 1, n) , suf_r = get(1, 1, n, r + 1, n);
int x =(rrh[high + 1] - rrh[high]) * (pre_l + suf_l) + (rrh[high + 1] - rrh[high]) * suf_r ;
int y =(rrh[high + 1] - rrh[high]) * (pre_r + suf_r) + (rrh[high + 1] - rrh[high]) * pre_l ;
x = min(x,y) % mod;
kq = (kq + x) % mod;
kq = ( kq + (sz - 2) * 2ll * calc(val + 1 ,nxt_val) % mod + calc(val + 1,nxt_val)) % mod;
}
kq = (kq + sz * calc(val,nxt_val - 1) % mod) % mod;
for(int idx : out[high + 1]) s.erase(idx);
}
cout << (kq + mod) % mod;
}
