#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,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){
            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;
        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;
}