#include <cstdio>
#include <stdio.h>
#include <stdbool.h>
#include <iostream>
#include <map>
#include <vector>
#include <climits>
#include <stack>
#include <string>
#include <queue>
#include <algorithm>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <cmath>
#include <cctype>
#include <bitset>
#include <iomanip>
#include <cstring>
#include <numeric>
#include <cassert>
using namespace std;
#define int long long
#define pii pair<int, int>
#define mp make_pair
#define pb push_back
#define fi first
#define se second
const int MOD = 1000003;
int n;
set<int> ss;
struct node{
int s, e, m, val;
node *l, *r;
node(int S, int E){
s = S, e = E, m = (s+e)/2;
val=0;
if (s!=e){
l = new node(s, m);
r = new node(m+1, e);
}
}
void up(int ind, int nv){
if (s==e)val=nv%MOD;
else{
if (ind<=m)l->up(ind, nv);
else r->up(ind, nv);
val = min(l->val, r->val);
}
}
int query(int left, int right){
if (s==left && e==right)return val;
if (right<=m)return l->query(left, right);
else if (left>m)return r->query(left, right);
else return min(l->query(left, m), r->query(m+1, right));
}
}*st;
int calc(int a, int b){
if (ss.empty())return 0;
int res=(((st->query(1, *ss.begin()-1)+st->query(*(--ss.end())+1, n))%MOD)*((b-a)%MOD))%MOD;
if (ss.size()==1)return res;
res=(res+(b*(b-a))%MOD+(((2*ss.size()-3)%MOD)*(((b)*(b+1)/2)%MOD-((a)*(a+1)/2)%MOD+MOD))%MOD)%MOD;
return (res+MOD)%MOD;
}
int32_t main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int ans=0, p=-1;
cin>>n;
st = new node(1, n);
map<int, vector<int> > m, done;
vector<int> vect(n+1), f(n+2, 0);
pii mx=mp(0, 0);
for (int i=1; i<=n; ++i)cin>>vect[i], st->up(i, vect[i]), m[vect[i]].pb(i), mx=max(mx, mp(vect[i], i));
for (int i=1; i<=mx.se; ++i)f[i]=max(f[i-1], vect[i]);
for (int i=n; i>=mx.se; --i)f[i]=max(f[i+1], vect[i]);
for (int i=1; i<=n; ++i){
ans=(ans+(f[i]*(f[i]-1)/2)%MOD-(vect[i]*(vect[i]-1)/2)%MOD+MOD)%MOD;
done[f[i]].pb(i);
}
for (auto c:m){
if (p!=-1)ans=(ans+calc(p, c.fi))%MOD;
for (auto a:c.se)ss.insert(a), st->up(a, LLONG_MAX/2);
for (auto a:done[c.fi])ss.erase(a);
p=c.fi;
}
cout<<ans;
}
