#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+5;
int a[N],n;
int f[N][2];
bool check(int m,bool flag = 0)
{
    int ty = 2;
    int L1 = 1,R1 = 0,L2 = 1,R2 = 0;
    for(int i = 1;i <= n;i++)
    {
        if(ty == 2)
        {
            if(R1-L1+1 + R2-L2+1 + m < a[i])
            {
                ty = 1;
                L1 = m-(a[i] - m - (R1-L1+1 + R2-L2+1))+1,R1 = m;
            }
            else
            {
                int x1 = L1-1,x2 = R1+R1-L1+1,x3 = L2+R1-L1,x4 = R2+R2-L2+1+R1-L1+1;
                if(a[i] >= x3) L1 = L2-1 + (a[i]-x3+1)/2+1;
                else if(a[i] >= x2) L1 = R1 + a[i]-x2+1;
                else if(a[i] >= x1) L1 = L1-1 + (a[i]-x1+1)/2+1;
                else L1 = a[i]+1;
                R1 = m;
                L2 = m+1,R2 = m;
            }
        }
        else
        {
            if(a[i] < L1)
            {
                ty = 2;
                L2 = R1+1;
                R2 = m;
                R1 = L1-1;
                L1 = a[i]+1;
            }
            else
            {
                R1 = L1 - 1;
                L1 = R1 - (a[i] - R1)+1;
            }
        }
        if(flag) cout<<ty<<" "<<L1<<" "<<R1<<" "<<L2<<" "<<R2<<"\n";
        if(ty == 1 && L1 < 0) return 0;
    }
    return ty == 2;
}
int main()
{
    ios::sync_with_stdio(false);cin.tie(0);
    cin>>n;
    for(int i = 1;i <= n;i++) cin>>a[i];
    int L = 1,R = 1e9;
    while(L < R)
    {
        int mid = (L+R>>1);
        if(check(mid)) R = mid;
        else L = mid+1;
    }
    cout<<L<<"\n";
    //check(L,1);
    return 0;
}