#include<bits/stdc++.h>
// #pragma GCC optimize("Ofast")
// #pragma GCC optimize("unroll-loops")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
using namespace std;
#define int long long
inline int read(){
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s*w;
}
int a[1<<20];
signed main()
{for(int T=1;T--;){
	int n=read();
	for(int i=1; i<=n; ++i) a[i]=read();
	int l=0,r=1e9,ans=r+1;
	// int l=2,r=2,ans=4;
	
	while(l<=r)
	{
		int mid=(l+r)>>1;
		int x=min(a[1],mid);
		int y=max(0ll,a[1]-mid);
		int z=mid;
		int o=(a[1]<=mid);
		// printf("%lld %lld %lld %lld %lld\n",1ll,x,y,z,o);
		for(int i=2; i<=n; ++i)
		{
			if(o)
			{
				if(a[i]<=x)
				{
					x=a[i],y=0,z=mid;
				}
				else if(a[i]<=(z-y)*2-x)
				{
					x=(a[i]+x+1)/2,y=0,z=mid;
				}
				else if(a[i]<=(z-y)*2-x+y)
				{
					x=(a[i]-(z-y)*2+x)+(z-y),y=0,z=mid;
				}
				else if(a[i]<=mid*2-y-x)
				{
					// puts("qwq");
					x=(a[i]+x+y+1)/2,y=0,z=mid;
				}
				else
				{
					// puts("owo");
					y=a[i]-(mid*2-y-x),x=mid,o=0;
				}
			}
			else
			{
				if(a[i]<=x-y)
				{
					z=x;
					x=a[i];
					o=1;
				}
				else
				{
					int oy=y;
					y=a[i]-(x-y);
					x-=oy;
				}
			}
			// printf("%lld %lld %lld %lld %lld\n",i,x,y,z,o);
		}
		if(o) ans=mid,r=mid-1;
		else l=mid+1;
	}
	
	printf("%lld\n",ans);
	
}return 0;}