#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long LL;
const int MAXN=2e5+5;
int n,a[MAXN];
bool check(int mid) {
	int k=0,len=0,l,r;
	for(int i=1;i<=n;++i) {
		int nk,nlen,nl,nr;
		if(k==0) {
			if(a[i]<=mid-len+1) nk=0,nlen=mid-a[i];
			else if(a[i]>mid+len) nk=1,nl=2*mid+len-a[i]+1,nr=mid;
			else nk=0,nlen=len-(a[i]-(mid-len)+1)/2;
		}
		if(k==1) {
			if(a[i]<l-1) nk=2,nl=a[i]+1,nr=l-1,nlen=mid-r;
			else if(a[i]==l-1) nk=0,nlen=mid-r;
			else nk=1,nl=2*l-a[i]-1,nr=l-1;
		}
		if(k==2) {
			if(a[i]<=l) nk=0,nlen=mid-a[i];
			else if(a[i]>mid+len+(r-l+1)) nk=1,nl=2*mid-a[i]+len+r-l+2,nr=mid;
			else if(a[i]>(mid-len)+(r-l+1)) nk=0,nlen=len-(a[i]-(mid-len)-(r-l+1)+1)/2;
			else if(a[i]>r+(r-l+1)) nk=0,nlen=mid-(a[i]-(r-l+1));
			else nk=0,nlen=mid-(l-1+(a[i]-(l-1)+1)/2);
		}
		k=nk,len=nlen,l=nl,r=nr;
		if(k==1&&l<=0) return 0;
	}
	return k!=1;
}
signed main() {
	ios::sync_with_stdio(0),cin.tie(0);
	cin>>n;
	for(int i=1;i<=n;++i) cin>>a[i];
	int l=0,r=1e9,ans=0;
	while(l<=r) {
		int mid=(l+r)>>1;
		if(check(mid)) r=mid-1,ans=mid;
		else l=mid+1;
	}
	cout<<ans;
	return 0;
}