#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ld long double
#define show(x,y) cout << y << " " << #x << endl;
#define show2(x,y,i,j) cout << y << " " << #x << " " << j << " " << #i << endl;
#define show3(x,y,i,j,p,q) cout << y << " " << #x << " " << j << " " << #i << " " << q << " " << #p << endl;
#define show4(x,y) for(auto it:y) cout << it << " "; cout << #x << endl;
typedef pair<int,int>pii;
typedef pair<pii,int>pi2;
mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count());
const int mod=1e6+3;
void solve(){
int n;
cin >> n;
int arr[n];
pii maxi={-1,-1};
for(int x=0;x<n;x++){
cin >> arr[x];
maxi=max(maxi,{arr[x],x});
}
int target[n];
int cur=0;
for(int x=0;x<=maxi.second;x++){
cur=max(cur,arr[x]);
target[x]=cur;
}
cur=0;
for(int x=n-1;x>=maxi.second;x--){
cur=max(cur,arr[x]);
target[x]=cur;
}
//show4(target,target);
int counter=0;
while(1){
pii mini={1e15,-1};
for(int x=0;x<n;x++){
if(arr[x]==target[x]) continue;
mini=min(mini,{arr[x],x});
}
//show(mini.second,mini.second);
if(mini.second==-1) break;
int lft=1e15;
int rgt=1e15;
for(int x=0;x<maxi.second;x++){
if(arr[x]<=mini.first) continue;
lft=min(lft,arr[x]);
}
for(int x=n-1;x>maxi.second;x--){
if(arr[x]<=mini.first) continue;
rgt=min(rgt,arr[x]);
}
counter+=lft+rgt+mini.first;
counter%=mod;
arr[mini.second]++;
//show4(arr,arr);
}
cout << counter;
}
int32_t main(){
ios::sync_with_stdio(0);
cin.tie(0);
//freopen("pieaters.in","r",stdin);
//freopen("pieaters.out","w",stdout);
int t=1;
//cin >> t;
while(t--){
solve();
}
}
