#include <bits/stdc++.h>
#define pii pair<int,int>
#define pb emplace_back
#define int long long
#define mk make_pair
#define reaD read
#define raed read
#define haed head
#define cotu cout
#define se second
#define fi first
#define itn int
//#define mid ((l+r)>>1)
//#define rs now<<1|1
//#define ls now<<1
using namespace std;
bool Mst;
const int Max=2e5+10;
const int mod=998244353;
const int inf=1e9+10;

inline int read(){
	int res=0,v=1;
	char c=getchar();
	while(c<'0'||c>'9'){v=(c=='-'?-1:1);c=getchar();}
	while(c>='0'&&c<='9'){res=(res<<3)+(res<<1)+(c^48);c=getchar();}
	return res*v;
}

int a[Max],n;

bool chk(int now){
	int opt=1,l=now+1,r=now,l1=now+1,r1=now;
	for(int i=1;i<=n;++i){
		if(opt==1){
			int len=r-l+1+r1-l1+1;
			if(now+len<a[i]){
				opt=-1;l=now-(a[i]-now-len)+1,r=now,l1=now+1,r1=now;
			}else{
				int res=0;
				if(l-1>=a[i])res=a[i];
				else if(a[i]-(l-1)<=2*(r-l+1))res=l-1+(a[i]-(l-1)+1)/2;
				else if(a[i]-(l-1)-2*(r-l+1)<l1-r)res=r+a[i]-(l-1)-2*(r-l+1);
				else if(a[i]-(l-1)-2*(r-l+1)-(l1-r)<=2*(r1-l1+1))res=l1-1+(a[i]-(l-1)-2*(r-l+1)-(l1-r)+1)/2;
				else if(a[i]-(l-1)-2*(r-l+1)-(l1-r)-2*(r1-l1+1)<=now-r1)res=r1+(a[i]-(l-1)-2*(r-l+1)-(l1-r)-2*(r1-l1+1));
				else res=now;
				opt=1;l=res+1;r=now;l1=now+1;r1=now;
			}
		}else{
			int lasl=l,lasr=r;
			if(a[i]<l){
				opt=1;l=a[i]+1,r=lasl-1;l1=lasr+1,r1=now;
			}else{
				opt=-1;l=lasl-(a[i]-l+1),r=lasl-1;l1=now+1,r1=now;
			}
		}
		l=min(l,now+1);l1=min(r1,now+1);
		if(l<1||l1<1)return 0;
	}
	if(opt==-1&&(r-l+1)+(r1-l1+1)>0)return 0;
	return 1;
} 

bool Med;
signed main(){
//	freopen("cow.in","r",stdin);
//	freopen("cow.out","w",stdout); 
	n=read();for(itn i=1;i<=n;++i)a[i]=read();
	int l=1,r=inf,ans=0;
	while(l<=r){
		int mid=(l+r)>>1;
		if(chk(mid))ans=mid,r=mid-1;
		else l=mid+1;
	}
	cout << ans << '\n';
	cerr<< "Time: "<<clock()/1000.0 << "s\n";
	cerr<< "Memory: " << (&Mst-&Med)/1000000.0 << "MB\n";
	return 0;
}
/*

*/