#include<bits/stdc++.h>
#define reg register
#define int long long
inline int read(){
    reg int x=0,k=1; reg char ch=getchar();
    while (ch<'0'||ch>'9') (ch=='-')&&(k=-1),ch=getchar();
    while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x*k;
}
const int N=3e5+10;
int n,a[N];
inline bool check(reg int lim){
    reg int l=1,r=0,L=1,R=0,lsty=lim,y=lim; // give get
    for (reg int i=1;i<=n;i++){
        // std::cerr<<l<<" "<<r<<" "<<y<<"\n";
        reg int t;
        if (y<=0) return 0;
        if (l<=r||L<=R){
            if (l<=r&&L<=R){
                if (a[i]<l) t=a[i];
                else if (a[i]<=r+r-l+1) t=l-1+((a[i]-(l-1)-1)/2+1);
                else{
                    reg int rest=a[i]-r-(r-l+1);
                    if (rest<=L-r-1) t=r+rest;
                    else if (rest>L-r-1+(R-L+1)*2) t=r+rest-(R-L+1);
                    else t=r+(rest-(L-r-1)-1)/2+1; 
                } 
            }else if (l<=r){
                if (a[i]<l) t=a[i];
                else if (a[i]>=r+r-l+1) t=a[i]-(r-l+1);
                else t=l-1+((a[i]-(l-1)-1)/2+1);
            }else if (L<=R){
                if (a[i]<L) t=a[i];
                else if (a[i]>=R+R-L+1) t=a[i]-(R-L+1);
                else t=L-1+((a[i]-(L-1)-1)/2+1);
            }
        }else t=a[i];
        l=t+1,r=y; L=lsty+1,R=lim,lsty=y;
        if (t>y) y=2*y-t; else y=lim;
    }
    return y==lim;
}
signed main(){
    n=read();
    for (reg int i=1;i<=n;i++) a[i]=read();
    reg int l=0,r=2e9,ans=-1;
    while (l<=r){
        reg int mid=l+r>>1;
        if (check(mid)) ans=mid,r=mid-1; else l=mid+1;
    }
    // check(4);
    printf("%lld\n",ans);
    return 0;
}