#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for (auto i=(a); i<(b); ++i)
#define iter(it,c) for (auto it = (c).begin(); it != (c).end(); ++it)
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef long long ll;
const int INF = 2147483647;
const ll DINF = 9000000000000000000;

int n;
vector<ll> arr;

// Optimal solution starting at the given index
ll opt(int at) {
    ll res = arr[at]+1,
       now = arr[at];
    int l = at, r = at;
    while (l > 0 || r < n-1) {
        ll lval = l-1 >= 0 ? arr[l-1] : DINF;
        ll rval = r+1 < n ? arr[r+1] : DINF;
        if (lval < rval) {
            res = max(arr[l-1]+1-now, res);
            now += arr[l-1];
            l--;
        } else {
            res = max(arr[r+1]+1-now, res);
            now += arr[r+1];
            r++;
        }
    }
    return res;
}

int main() {
    srand(1337);

    cin >> n;
    arr = vector<ll>(n);
    vector<pair<ll,int> > loc(n);
    rep(i,0,n) {
        cin >> arr[i];
        loc[i] = make_pair(arr[i], i);
    }
    sort(loc.begin(), loc.end());

    ll best = DINF;

    int iters = 1000;

    // Random indices
    rep(it,0,iters) {
        best = min(best, opt(rand() % n));
    }
    // Leftmost indices
    for (int at = 0, it = 0; at < n && it < iters; at++, it++) {
        best = min(best, opt(at));
    }
    // Rightmost indices
    for (int at = n-1, it = 0; at >= 0 && it < iters; at--, it++) {
        best = min(best, opt(at));
    }
    // Smallest values
    for (int at = 0, it = 0; at < n && it < iters; at++, it++) {
        best = min(best, opt(loc[at].second));
    }
    // Largest values
    for (int at = n-1, it = 0; at >= 0 && it < iters; at--, it++) {
        best = min(best, opt(loc[at].second));
    }

    cout << best << endl;

    return 0;
}