#include <bits/stdc++.h>

using std::cin;
using std::cout;
using std::endl;
using std::vector;
using std::string;
using ll = long long;
using vi = vector<ll>;
using vii = vector<vi>;
using pii = std::pair<ll,ll>;

#define rep(i,j,k) for(ll i=ll(j); i<ll(k); i++)
#define REP(i,j,k) for(ll i=ll(j); i<=ll(k); i++)
#define per(i,j,k) for(ll i=ll(j); i>=ll(k); i--)
#define ln "\n"
#define pb emplace_back
#define mp std::make_pair
#define all(a) a.begin(),a.end()
#define mtp std::make_tuple

constexpr ll inf = (1ll<<60);
constexpr ll mod = 1e6+3;

int main(){
    cin.tie(nullptr);
    std::ios::sync_with_stdio(false);
    ll N; cin >> N;
    vi H(N);
    rep(i,0,N) cin >> H[i];
    vi goal(N,inf);
    ll max = 0;
    rep(i,0,N){
        max = std::max(max, H[i]);
        goal[i] = std::min(goal[i], max);
    }
    max = 0;
    per(i,N-1,0){
        max = std::max(max, H[i]);
        goal[i] = std::min(goal[i], max);
    }
    ll ans = 0;
    rep(i,0,N){
        ans += (goal[i]-1+H[i])*(goal[i]-H[i])/2;
        ans %= mod;
        ans += (goal[i]+1+H[i])*(goal[i]-H[i])/2;
        ans %= mod;
        ans += (goal[i]+1+H[i])*(goal[i]-H[i])/2;
        ans %= mod;
    }
    std::set<ll> set;
    rep(i,0,N){
        ll el = *set.begin();
        if(el > H[i]){
            ans -= (el+1+H[i])*(el-H[i])/2;
            ans %= mod;
            ans += el*(el-H[i]);
            ans %= mod;
        }
        set.insert(H[i]);
    }
    set.clear();
    per(i,N-1,0){
        ll el = *set.begin();
        if(el > H[i]){
            ans -= (el+1+H[i])*(el-H[i])/2;
            ans %= mod;
            ans += el*(el-H[i]);
            ans %= mod;
        }
        set.insert(H[i]);
    }
    {
        std::map<ll,ll> mem;
        rep(i,0,N) mem[H[i]] = mem[goal[i]] = 0;
        ll cnt = 0;
        vi rev;
        for(auto &el: mem){
            el.second = cnt++;
            rev.pb(el.first);
        }
        ll n = cnt;
        vi sum(n);
        rep(i,0,N){
            sum[mem[H[i]]]++;
            sum[mem[goal[i]]]--;
        }
        rep(i,1,n) sum[i] += sum[i-1];
        rep(i,0,n){
            if(sum[i]){
                ans -= (rev[i+1]+1+rev[i])*(rev[i+1]-rev[i])/2;
                ans %= mod;
                ans += rev[i+1]*(rev[i+1]-rev[i]);
                ans %= mod;
            }
        }
    }
    if(ans < 0) ans += mod;
    cout << ans << ln;
}