#include<bits/stdc++.h>
using namespace std;
// #define int long long
#define rep(i,j,k) for(int i=(j);i<=(k);i++)
#define per(i,j,k) for(int i=(j);i>=(k);i--)
#define pb emplace_back
#define fi first
#define se second
using vi=vector<int>;
using pi=pair<int,int>;

template<typename T> bool chmin(T &x,const T &y){
	if(y<x){
		x=y;
		return true;
	}
	return false;
}
template<typename T> bool chmax(T &x,const T &y){
	if(y>x){
		x=y;
		return true;
	}
	return false;
}

namespace Debug{
	template<typename T> void _debug(char *s, T x){
		cerr<< s <<" = "<< x <<endl;
	}
	template<typename T, typename ...Ar> void _debug(char *s, T x, Ar... y){
		while(*s != ',') cerr<< *s++;
		cerr<<" = "<< x <<",";
		_debug(s+1, y...);
	}
}
using namespace Debug;
#define gdb(...) _debug((char*)#__VA_ARGS__, __VA_ARGS__)

signed main(){
	ios::sync_with_stdio(0);cin.tie(0);
	
	int n; cin>>n;
	vi a(n+1);
	rep(i,1,n){
		cin>>a[i];
	}
	
	auto chk=[&](int t){
		auto calc=[&](int x,pi rg){
			if(x <= rg.fi){
				return x;
			}
			if(x >= rg.se*2 - rg.fi){
				return x-(rg.se-rg.fi);
			}
			return rg.fi + (x-rg.fi+1)/2;
		};
		tuple<bool, pi, pi> lst{0, {t, t}, {t, t}};
		rep(i,1,n){
			auto [op, rg0, rg1]=lst;
			// gdb(t, i, op, rg0.fi, rg0.se, rg1.fi, rg1.se);
			if(op==0){
				int t0=calc(a[i], rg1);
				int t1=calc(t0, rg0);
				// gdb(i, t0, t1, t);
				if(t1 <= t){
					lst = {0, {t1, t}, {t, t}};
				}
				else{
					if(t-(t1-t)<0){
						return false;
					}
					lst = {1, {t-(t1-t), t}, {-1, -1}};
				}
			}
			else{
				if(a[i] <= rg0.fi){
					lst = {0, {a[i], rg0.fi}, {rg0.se, t}};
				}
				else{
					int t0 = rg0.fi-(a[i]-rg0.fi);
					if(t0<0){
						return false;
					}
					lst = {1, {t0, rg0.fi}, {-1, -1}};
				}
			}
		}
		return get<0>(lst) == 0;
	};
	
	int l=0, r=*max_element(a.begin(), a.end());
	while(l<r){
		int mid=(l+r)/2;
		if(chk(mid)){
			r=mid;
		}
		else{
			l=mid+1;
		}
	}
	cout<< l <<'\n';
}