#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int n,h[N];
inline bool check(int mid){
	int lt=mid,le=0,o=1;
	for(int i=1;i<=n;i++){
		if(o){
			int now=h[i],nt=-1,ne=-1;
			if(now<=lt)	lt=now,le=0,o=1;
			else{
				now-=lt;
				if(now<=2*(mid-lt))	lt+=(now+1)/2,le=0,o=1;
				else	le=now-2*(mid-lt),lt=mid,o=0;
			}
		}
		else{
			if(lt-le<1)	return 0;
			if(h[i]<=lt-le)	lt=h[i]+le,le=0,o=0;
			else	lt=lt-le,le=h[i]-lt,o=1;
		}
	}
	if(!o)	return 0;
	return 1;
}
int main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++)	cin>>h[i];
	int l=1,r=1e9;
	while(l<r){
		int mid=(l+r)/2;
		if(check(mid))	r=mid;
		else	l=mid+1;
	}
	cout<<l<<endl;
	return 0;
}