#include <bits/stdc++.h>
#define int long long
#define ll long long
#define all(lpv) lpv.begin(), lpv.end()
#define fi first
#define se second
using namespace std;
typedef pair<int,int> pii;
const int N = 1e6 + 5;
const int oo = 1e16;
const int mod = 1e6 + 3;
int n, m, a[N], pf[N], sf[N], st[N << 1], des[N], le[N], ri[N];
void update(int i,int x){
i += n - 1;
st[i] = x;
while(i > 1){
i /= 2;
st[i] = min(st[i << 1], st[i << 1|1]);
}
}
int get(int l,int r){
if(l > r) return oo;
r++;
int ret = oo;
for(l += n - 1, r += n - 1; l < r; l /= 2, r /= 2){
if(l & 1) ret = min(ret, st[l ++]);
if(r & 1) ret = min(ret, st[-- r]);
}
return ret;
}
void add(int &x,int y){
x = (x + y) % mod;
}
vector<int> open[N], close[N], rrh;
int spe;
int lt(int u,int v){
if(!v) return 1;
int x = u;
int kq = 1;
while(v){
if(v & 1) kq = kq * x % mod;
x = x * x % mod;
v /= 2;
}
return kq;
}
int cal(int l,int r){
return (l + r) % mod * spe % mod * (r - l + 1) % mod % mod;
}
signed main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define task "v"
if(fopen(task ".inp","r")){
freopen(task ".inp","r",stdin);
freopen(task ".out","w",stdout);
}
cin >> n;
spe = lt(2ll, mod - 2);
for(int i = 1; i <= n; i ++){
cin >> a[i];
rrh.push_back(a[i]);
}
for(int i = 1; i <= n; i ++){
le[i] = le[i - 1] + (pf[i] > a[i] ? pf[i] - a[i] : 0);
pf[i] = max(a[i], pf[i - 1]);
update(i, a[i]);
}
for(int i = n; i >= 1; i --){
ri[i] = ri[i + 1] + (sf[i] > a[i] ? sf[i] - a[i] : 0);
sf[i] = max(sf[i + 1], a[i]);
}
int pos = 1, ans = oo;
for(int i = 1; i <= n; i ++){
int val = max(pf[i], sf[i]) - a[i] + le[i - 1] + ri[i + 1];
if(val < ans){
ans = val;
pos = i;
}
}
sort(all(rrh)); rrh.resize(unique(all(rrh)) - rrh.begin());
m = (int)rrh.size();
for(int i = 1; i <= n; i ++) a[i] = lower_bound(all(rrh), a[i]) - rrh.begin() + 1;
ans = 0;
des[pos] = lower_bound(all(rrh), max(pf[pos], sf[pos])) - rrh.begin() + 1;
for(int i = 1; i < pos; i ++) des[i] = lower_bound(all(rrh), pf[i]) - rrh.begin() + 1;
for(int i = pos + 1; i <= n; i ++) des[i] = lower_bound(all(rrh), sf[i]) - rrh.begin() + 1;
for(int i = 1; i <= n; i ++){
// cerr << i << " " << a[i] << " " << des[i] << " p\n";
if(a[i] < des[i]){
open[a[i]].push_back(i);
}
close[des[i]].push_back(i);
}
ans = 0;
set<int> col;
for(int k = 1; k <= m; k ++){
for(auto j : close[k]){
if(col.find(j) != col.end()) col.erase(j);
update(j, oo);
}
for(auto j : open[k]){
col.insert(j);
update(j, oo);
}
if(col.empty()) continue;
int tmp = rrh[k - 1], nxt = rrh[k];
int x = (*col.begin());
int y = (*col.rbegin());
if(x == y){
int val = ((get(1, x - 1) + get(x + 1, n)) * (nxt - tmp) % mod + cal(tmp, nxt - 1)) % mod;
add(ans, val);
}else{
int cx = ((get(1, x - 1) + get(x + 1, n)) * (nxt - tmp));
int cy = ((get(1, y - 1) + get(y + 1, n)) * (nxt - tmp));
// cerr << cx << " " << cy << " q\n"
int val = (min(cx + get(y + 1, n) * (nxt - tmp),
cy + get(1, x - 1) * (nxt - tmp)) % mod + 3 * cal(tmp, nxt - 1) % mod + (nxt - tmp)) % mod;
// cerr << val << " " << cx << " " << 2 * cal(tmp, nxt - 1) % mod + (nxt - tmp) << " " << get(y + 1, n) << " r\n";
add(ans, val);
}
// cerr << k << " " << ans << " r\n";
int cnt = (int)col.size();
int val = max(0ll, cnt - 2) * (3 * cal(tmp, nxt - 1) % mod + 2 * (nxt - tmp) % mod) % mod;
add(ans, val);
}
cout << ans;
}
