#include<iostream>
#include<vector>
#include<cassert>
using namespace std;
int N,H[2<<17];
bool check(int T)
{
	vector<pair<int,int> >X;
	bool lft=false;
	for(int i=0;i<N;i++)
	{
		if(X.empty())
		{
			if(H[i]>T)
			{
				int l=2*T-H[i];
				if(l<0)return false;
				X.push_back(make_pair(l,T));
				lft=true;
			}
			else
			{
				if(H[i]<T)X.push_back(make_pair(H[i],T));
				lft=false;
			}
		}
		else if(lft)
		{
			assert(X.size()==1);
			auto[l,r]=X[0];
			X.clear();
			if(l>=H[i])
			{
				if(H[i]<l)X.push_back(make_pair(H[i],l));
				if(r<T)X.push_back(make_pair(r,T));
				lft=false;
			}
			else
			{
				int nl=2*l-H[i];
				if(nl<0)return false;
				X.push_back(make_pair(nl,l));
				lft=true;
			}
		}
		else
		{
			int pos=0;
			int rest=H[i];
			if(rest==0)
			{
				X.clear();
				if(0<T)X.push_back(make_pair(0,T));
				lft=false;
			}
			else
			{
				for(int j=0;j<X.size();j++)
				{
					auto[l,r]=X[j];
					if(rest<=l-pos)
					{
						X.clear();
						if(pos+rest<T)X.push_back(make_pair(pos+rest,T));
						lft=false;
						rest=0;
						break;
					}
					rest-=l-pos;
					if(rest<=2*(r-l))
					{
						int u=l+(rest+1)/2;
						X.clear();
						if(u<T)X.push_back(make_pair(u,T));
						lft=false;
						rest=0;
						break;
					}
					rest-=2*(r-l);
					pos=r;
				}
				if(rest>0&&rest<=T-pos)
				{
					X.clear();
					if(pos+rest<T)X.push_back(make_pair(pos+rest,T));
					lft=false;
					rest=0;
				}
				if(rest>0)
				{
					int nl=T-rest;
					if(nl<0)return false;
					X.clear();
					X.push_back(make_pair(nl,T));
					lft=true;
				}
			}
		}
	}
	if(lft)return false;
	return true;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin>>N;
	for(int i=0;i<N;i++)cin>>H[i];
	int L=-1,R=(int)1e9;
	while(R-L>1)
	{
		int M=(L+R)/2;
		if(check(M))R=M;
		else L=M;
	}
	cout<<R<<endl;
}