#include<iostream>
#include<vector>
using namespace std;

#define int long long
typedef long long ll;
const int MOD = 1e6 + 3;
const ll INF = 1e18;
const int MAXN = 5005;

int h[MAXN], a[MAXN];
int n;

signed main(){
	freopen("Real.in", "r", stdin);
	freopen("Real.out", "w", stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for(int i = 0;i < n;i ++) cin >> h[i];
    ll res = INF;
    for(int p = 0;p < n;p ++){
        for(int i = 0;i < n;i ++) a[i] = h[i];
        ll cost = 0;
        bool ok = true;
        for(int i = n - 2;i >= p;i --){
            while(a[i] < a[i + 1]){
                ll minx = INF;
                bool flag = false;
                for(int j = 0;j < i;j ++){
                    if(a[j] > a[i]){
                        for(int k = i + 1;k < n;k ++){
                            if(a[k] > a[i]){
                                ll s = a[j] + a[i] + a[k];
                                if(s < minx){
                                    minx = s;
                                    flag = true;
                                }
                            }
                        }
                    }
                }
                if(!flag){
                	ok = false;
					break;
				}
                cost += minx;
                a[i] ++;
            }
            if(!ok) break;
        }
        if (!ok) continue;
        for(int i = 1;i <= p;i ++){
            while(a[i] < a[i - 1]){
                ll minx = INF;
                bool flag = false;
                for(int j = 0;j < i;j ++){
                    if(a[j] > a[i]) {
                        for(int k = i + 1;k < n;k ++){
                            if(a[k] > a[i]) {
                                ll s = a[j] + a[i] + a[k];
                                if(s < minx){
                                    minx = s;
                                    flag = true;
                                }
                            }
                        }
                    }
                }
                if(!flag){
                	ok = false;
					break;
				}
                cost += minx;
                a[i] ++;
            }
            if(!ok) break;
        }
        if(ok) res = min(res, cost);
    }
    cout << res % MOD << '\n';
    return 0;
}