#include <bits/stdc++.h>
using namespace std;
#define rep(i, l, r) for(int i = (l); i < (r); ++i)
#define mp make_pair
#define mt make_tuple
#define ff first
#define ss second
#define all(v) begin(v), end(v)
#define rall(v) rbegin(v), rend(v)
#define sz(v) (int)v.size()
#define pb push_back
#define eb emplace_back
#define compact(v) v.erase(unique(all(v)), end(v))
#define dbg(x) "[" #x " = " << (x) << "]"
template<typename T>
bool minimize(T& a, const T& b){
if(a > b) return a = b, true;
return false;
}
template<typename T>
bool maximize(T& a, const T& b){
if(a < b) return a = b, true;
return false;
}
using ll = long long;
using db = double;
using ld = long double;
using pi = pair<int, int>;
using pl = pair<ll, ll>;
using vi = vector<int>;
using vb = vector<bool>;
using vl = vector<ll>;
using vc = vector<char>;
using vd = vector<db>;
using vpi = vector<pi>;
using vpl = vector<pl>;
const int mod = 1e6 + 3;
//struct mint{
// int v;
// mint(int v = 0) : v(v) {
// if(v >= mod) v %= mod;
// }
//
// mint& operator += (const mint& o){
// v += o.v;
// if(v >= mod) v -= mod;
// return *this;
// }
//
// mint& operator -= (const mint& o){
// v -= o.v;
// if(v < 0) v += mod;
// return *this;
// }
//
// mint& operator *= (const mint& o){
// v = 1LL * v * o.v % mod;
// return *this;
// }
//
// friend bool operator == (const mint& a, const mint& b){ return a.v == b.v; }
// friend bool operator != (const mint& a, const mint& b){ return a.v != b.v; }
//
// friend mint operator + (mint a, const mint& b){ return a += b; }
// friend mint operator - (mint a, const mint& b){ return a -= b; }
// friend mint operator * (mint a, const mint& b){ return a *= b; }
//
// friend ostream& operator << (ostream& out, const mint& o){ return out << o.v; }
//};
const int MAX = 1e6 + 5;
const int inf = 1e9 + 9;
struct MinSegmentTree{
vpi st;
int n;
MinSegmentTree(int n) : n(n), st(n << 2) {
build(1, 0, n-1);
}
void build(int id, int l, int r){
if(l == r){
st[id] = mp(inf, l);
} else{
int mid = l + r >> 1;
build(id << 1, l, mid);
build(id << 1 | 1, mid + 1, r);
st[id] = min(st[id << 1], st[id << 1 | 1]);
}
}
void update(int id, int l, int r, int pos, int val){
if(l == r) st[id].ff = val;
else{
int mid = l + r >> 1;
if(pos <= mid) update(id << 1, l, mid, pos, val);
else update(id << 1 | 1, mid + 1, r, pos, val);
st[id] = min(st[id << 1], st[id << 1 | 1]);
}
}
int query(int id, int l, int r, int u, int v){
if(v < l || u > r) return inf;
if(u <= l && r <= v) return st[id].ff;
int mid = l + r >> 1;
return min(query(id << 1, l, mid, u, v), query(id << 1 | 1, mid + 1, r, u, v));
}
void refine(int threshold){
while(st[1].ff <= threshold){
update(1, 0, n-1, st[1].ss, inf);
}
}
void update(int pos, int val){
update(1, 0, n-1, pos, val);
}
};
int N, H[MAX], f[MAX], fl[MAX], fr[MAX];
int main(){
ios_base::sync_with_stdio(0);
#ifdef LOCAL
freopen("task.inp", "r", stdin);
freopen("task.out", "w", stdout);
#endif //LOCAL
cin >> N;
for(int i = 0; i < N; ++i) cin >> H[i];
int mx_pos = max_element(H, H + N) - H;
stack<int> st;
vector<pair<int, int>> bad;
if(mx_pos > 0){
f[mx_pos] = H[mx_pos];
st.push(mx_pos);
for(int i = mx_pos - 1; i >= 0; --i){
while(!st.empty() && H[st.top()] < H[i]) st.pop();
st.push(i);
}
int lo = st.top(); st.pop();
while(!st.empty()){
int hi = st.top(); st.pop();
for(int i = lo; i < hi; ++i) f[i] = H[lo];
if(lo+1 < hi) bad.eb(lo+1, hi-1);
lo = hi;
}
}
if(mx_pos + 1 < N){
st.push(mx_pos);
for(int i = mx_pos + 1; i < N; ++i){
while(!st.empty() && H[st.top()] < H[i]) st.pop();
st.push(i);
}
int hi = st.top(); st.pop();
while(!st.empty()){
int lo = st.top(); st.pop();
for(int i = lo + 1; i <= hi; ++i) f[i] = H[hi];
if(lo+1 < hi) bad.eb(lo+1, hi-1);
hi = lo;
}
}
MinSegmentTree tr(N);
for(int i = 0; i < N; ++i) {
// cout << f[i] << ' ';
tr.update(i, H[i]);
}
// cout << '\n';
vector<tuple<int, int, int>> events;
multiset<int> online;
for(int i = 0; i < sz(bad); ++i){
int l, r;
tie(l, r) = bad[i];
for(int j = l; j <= r; ++j){
events.eb(H[j], -1, j);
}
events.eb(min(H[l-1], H[r+1]), +1, i);
// cout << dbg(l) << dbg(r) << dbg(H[l-1]) << dbg(H[r+1]) << '\n';
}
sort(all(events));
int cnt = 0;
ll ans = 0;
for(int i = 0; i < sz(events); ++i){
int tm, type, id;
tie(tm, type, id) = events[i];
tr.refine(tm);
if(type == -1){
++cnt;
online.insert(id);
} else{
int l, r; tie(l, r) = bad[id];
cnt -= (r - l + 1);
for(int j = l; j <= r; ++j) online.erase(j);
}
if(i == sz(events) - 1) continue;
int nxt_tm, nxt_type, nxt_id;
tie(nxt_tm, nxt_type, nxt_id) = events[i+1];
if(tm != nxt_tm){
assert(cnt > 0);
ll times = nxt_tm - tm;
int L = *online.begin();
int R = *online.rbegin();
int A = tr.query(1, 0, N-1, 0, L-1);
int B = tr.query(1, 0, N-1, R+1, N-1);
if(A > B) swap(A, B);
if(cnt == 1){
int A = tr.query(1, 0, N-1, 0, L-1);
int B = tr.query(1, 0, N-1, R+1, N-1);
if(A > B) swap(A, B);
// cout << "haha\n";
// cout << dbg(A) << dbg(B) << dbg(tm) << dbg(times) << '\n';
ll cur = (A + B) * times + tm * times + 1LL * times * (times - 1) / 2;
(ans += (cur % mod)) %= mod;
continue;
}
ll qll = tr.query(1, 0, N-1, 0, L-1);
ll qlr = tr.query(1, 0, N-1, L+1, N-1);
ll qrl = tr.query(1, 0, N-1, 0, R-1);
ll qrr = tr.query(1, 0, N-1, R+1, N-1);
// cout << dbg(qll) << dbg(qlr) << dbg(qrl) << dbg(qrr) << '\n';
// cout << dbg(A) << dbg(B) << dbg(tm) << dbg(times) << dbg(cnt) << '\n';
ll overtime = 1LL * times * (times - 1) / 2;
ll case1 = (qll + qlr + qrr) * times + 3 * tm * times + times + overtime * 3; //constructing the left end point first
ll case2 = (qrl + qrr + qll) * times + 3 * tm * times + times + overtime * 3; //constructing the right end point first
// cout << dbg(case1) << dbg(case2) << '\n';
ll two_endpoints = min(case1, case2);
ll middle_part = 3 * tm * times + 2 * times + overtime * 3;
// cout << dbg(two_endpoints) << ' ' << dbg(middle_part * (cnt - 2)) << '\n';
two_endpoints %= mod;
middle_part %= mod;
middle_part = 1LL * middle_part * (cnt - 2) % mod;
(ans += (two_endpoints + middle_part) % mod) %= mod;
}
// cout << '\n';
}
cout << ans << '\n';
return 0;
}
/*
5
5 1 1 1 5
132
11
4 1 2 3 6 5 1 4 1 3 2
94
*/
