#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define FOR(i,a,b) for (int i = (a); i < (b); i++)
using namespace std;
using namespace __gnu_pbds;
using ll=long long;
using ld=long double;
using vi=vector<int>;
template<class T> using oset =tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update> ;
//上
const int inf = 1e9+10;
int f(int x,int l,int r){
    if( x < l) return x;
    if( l-1+2*(r-l+1) <= x){
        x -=(r-l+1);
        return x;
    }
    return (l-1)+(x-(l-1)+1)/2;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin >> n;
    vector<ll> v(n);
    FOR(i,0,n) cin >> v[i];
    int l = 0;
    int r = 1e9;
    int ans = 1e9;
    while(l <= r){
        int mid =(l+r)/2;
        int req = 0;
        int lx = inf;
        int rx = inf;
        int ly = inf;
        int ry = inf;
        bool ok = true;
        for(int i = 0; i < n; i++){
            if(req == 0){
                int x = v[i];
                if(lx <= rx){
                    x = f(x,lx,rx);
                }
                if(ly <= ry){
                    x = f(x,ly,ry);
                }
                if(x <= mid){
                    req = 0;
                    lx = x+1;
                    rx = mid;
                    ly = inf;
                    ry = inf;
                }else{
                    req = 1;
                    int co = (x-mid);
                    if(mid>= co){
                        lx = mid-co+1;
                        rx = mid;
                    }else{
                        ok = false;
                        break;
                    }
                }
            }else{
                if(v[i] < lx){
                    req = 0;
                    ly = rx+1;
                    ry = mid;
                    rx = lx-1;
                    lx =v[i]+1;
                }else{
                    req = 1;
                    int diff = (rx-lx);
                    rx = lx-1;
                    lx = rx-diff;
                    if(lx <= 0){
                        ok = false;
                        break;
                    }
                }
            }
        }
        if(req) ok = false;
        if(ok){
            ans = mid;
            r = mid-1;
        }else l= mid +1;
    }
    cout <<ans <<'\n';
}