#include <bits/stdc++.h>
#define nl "\n"
#define no "NO"
#define yes "YES"
#define fi first
#define se second
#define vec vector
#define task "main"
#define _mp make_pair
#define ii pair<int, int>
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define evoid(val) return void(std::cout << val)
#define FOR(i, a, b) for(int i = (a); i <= (b); ++i)
#define FOD(i, b, a) for(int i = (b); i >= (a); --i)
#define unq(x) sort(all(x)); x.resize(unique(all(x)) - x.begin())
using namespace std;
template<typename U, typename V> bool maxi(U &a, V b) {
if (a < b) { a = b; return 1; } return 0;
}
template<typename U, typename V> bool mini(U &a, V b) {
if (a > b) { a = b; return 1; } return 0;
}
const int N = (int)1e6 + 9;
const int mod = (int)1e6 + 3;
void prepare(); void main_code();
int main() {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
if (fopen(task".inp", "r")) {
freopen(task".inp", "r", stdin);
freopen(task".out", "w", stdout);
}
const bool MULTITEST = 0; prepare();
int num_test = 1; if (MULTITEST) cin >> num_test;
while (num_test--) { main_code(); }
}
void prepare() {};
int n, dest[N], a[N], L[N], R[N];
long long dpL[N], dpR[N];
const long long INF = (long long)1e16;
namespace SUB1{
vector<int> qr[107];
void sol() {
long long ans=0;
FOR(i, 1, n) if (a[i]!=dest[i]){
qr[a[i]].push_back(i);
}
// FOR(i, 1, n) cout << dest[i] << ' '; cout << nl;
FOR(i, 1, 99) if (sz(qr[i])) {
ans += 1LL * i * sz(qr[i]);
auto g = qr[i];
sort(all(g));
// cout << i << ": ";
// for(int j : g) cout << j << ' '; cout << nl;
set<int> s;
int lst=0;
int idx=0;
for(int i:g){
while(lst+1<i){
++lst;
s.insert(a[lst]);
}
L[idx++]=*s.upper_bound(a[i]);
}
s.clear();
reverse(all(g));
idx=sz(g)-1;
lst=n+1;
for(int i:g){
while(lst-1>i){
--lst;
s.insert(a[lst]);
}
R[idx--]=*s.upper_bound(a[i]);
}
reverse(all(g));
int m = sz(g);
if (m == 1) {
int p=g[0];
ans+=L[0]+R[0];
++a[p];
if (a[p]!=dest[p]){
qr[i+1].push_back(p);
}
// cout << "ans: " << ans << nl;
continue;
}
long long h = i;
dpL[0] = L[0] + (i + 1);
for(int i = 1; i < m; ++i) {
// tinh dpL[i]
dpL[i] = dpL[i-1] + L[i] + (h + 1);
for(int j = 0; j < i; ++j)
dpL[i] = min(dpL[i], (j>0?dpL[j-1]:0) + L[j]
+ (h+1) + (h * 2 + 2) * (i-j));
}
// if (h == 8) {
// FOR(i, 0, m - 1) cerr << dpL[i] << ' '; cerr << nl;
// }
dpR[m - 1] = R[m - 1] + (i + 1);
for(int i = m - 2; i >= 0; --i) {
dpR[i] = dpR[i+1] + R[i] + (h + 1);
for(int j = i + 1; j < m; ++j)
dpR[i] = min(dpR[i], (j<m-1?dpR[j+1]:0) + R[j]
+ (h+1) + (h * 2 + 2) * (j-i));
}
long long res=INF;
FOR(i, 0, m - 1) {
long long s = L[i] + R[i];
// chi phi
s += (i > 0 ? dpL[i-1] : 0);
s += (i < m - 1 ? dpR[i + 1] : 0);
res = min(res, s);
}
ans += res;
for(int i : g) {
++a[i];
if (a[i] != dest[i])
qr[h + 1].push_back(i);
}
// cout << "ans: " << ans << nl;
}
cout << ans%mod;
}
};
void main_code() {
cin >> n;
int mx = 0;
int f=-1, l=-1;
for(int i = 1; i <= n; ++i) {
cin >> a[i];
if (a[i] < mx) continue;
if (a[i] > mx) {
f=l=i; mx=a[i];
} else {
l=i;
}
}
// (f..l) = mx
// (1..f) tang dan
// (f, n) giam dan
for(int i = 1, mx = 0; i <= f; ++i) {
mx=max(mx,a[i]);
dest[i]=mx;
}
for(int i = n, mx = 0; i >= l; --i) {
mx=max(mx,a[i]);
dest[i]=mx;
}
FOR(i, f, l) dest[i] = mx;
if (*max_element(a + 1, a + n + 1) <= 100) {
return SUB1::sol(), void();
}
}
/* Let the river flows naturally */
