#include <bits/stdc++.h>
using namespace std;
const int N=210000,INF=1e9;
int n;
int a[N];
bool check(int x){
	bool op=1;
	int t=0,tm=0;
	int la=1,ra=0,lb=1,rb=0;
	for(int i=1;i<=n;i++){
		if(op==0){
			int ht=t,htm=tm;
			if(a[i]+tm<=t){
				op=1;
				t=0,tm=0;
				la=a[i]+1,ra=ht-htm,lb=ht+1,rb=x;
			}
			else{
				t=ht-htm,tm=a[i]+htm-ht;
				if(tm>t)
					return 0;
			}
		}
		else{
			int res=a[i];
			if(la<=res){
				if(2*ra+2*(ra-la+1)<=res)
					res-=2*(ra-la+1);
				else
					res=la+(res-la)/2;
			}
			if(lb<=res){
				if(2*rb+2*(rb-lb+1)<=res)
					res-=2*(rb-lb+1);
				else
					res=lb+(res-lb)/2;
			}
			if(res<=x)
				la=1,ra=0,lb=res+1,rb=x;
			else{
				op=0;
				t=x,tm=res-x;
				la=1,ra=0,lb=1,rb=0;
			}
		}
	}
	return tm==0;
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	int l=0,r=INF;
	while(l!=r){
		int mid=(l+r)>>1;
		if(check(mid))
			r=mid;
		else
			l=mid+1;
	}
	printf("%d",l);
	return 0;
}