#include<bits/stdc++.h>
using namespace std;
const int N=200009;
int n,a[N];
#define int long long
#define pii pair<int,int>
#define mp(x,y) make_pair(x,y)
pii hp1,hp2,nd,I=mp(1,0);
bool judge(int mid){
	int tp=1,l,r,l2,r2,len,aa,t;
	hp1=hp2=I;
	for(int i=1;i<=n;i++){
		aa=a[i];
		if(tp==1){
			l=hp1.first; r=hp1.second;
			if(aa<l){ l=aa+1; r=mid; hp1=mp(l,r); hp2=I; }
			else if(aa<=r+(r-l+1)){ l=l-1+(aa-l+1+1)/2+1; r=mid; hp1=mp(l,r); hp2=I; }
			else if(hp2==I){
				if(aa<=mid+(r-l+1)){ l=aa-(r-l+1)+1; r=mid; hp1=mp(l,r); hp2=I; }
				else{
					tp=2;
					len=aa-mid-(r-l+1);
					r=mid; l=mid-len+1;
					hp1=hp2=I;
				}
			}
			else{
				//r
				l2=hp2.first; r2=hp2.second; hp2=I;
				aa-=r+(r-l+1);
				if(aa<l2-r){ l=r+aa; r=mid; hp1=mp(l,r); }
				else if(aa<r2-r+(r2-l2+1)){
					l=l2-1+(aa-(l2-r-1)+1)/2+1; r=mid;
					hp1=mp(l,r);
				}
				else{
					aa-=(r2-r)+(r2-l2+1);
					if(r2+aa<=mid){ l=r2+aa+1; r=mid; hp1=mp(l,r); }
					else{
						tp=2;
						len=r2+aa-mid;
						r=mid; l=r-len+1;
						hp1=I;
					}
				}
			}
		}
		else{
			t=l-1;
			if(t<0) return false;
			if(aa<=t){
				tp=1;
				hp1=mp(aa+1,t);
				hp2=mp(r+1,mid);
			}
			else{
				len=aa-t;
				r=t; l=t-len+1;
			}
		}
	}
	if(tp==2) return false;
	return true;
}
signed main(){
	std::ios::sync_with_stdio(false);
	cin.tie(0);
	int l=0,r=0,re,mid;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		r=max(r,a[i]);
	}
	re=r;
	while(l<=r){
		mid=(l+r)/2;
		if(judge(mid)) re=mid,r=mid-1;
		else l=mid+1;
	}
	cout<<re;
	return 0;
}

answer.code: In function ‘int main()’:
answer.code:72:22: error: no matching function for call to ‘max(long long int&, int&)’
   72 |                 r=max(r,a[i]);
      |                   ~~~^~~~~~~~
In file included from /usr/include/c++/14/algorithm:60,
                 from /usr/include/x86_64-linux-gnu/c++/14/bits/stdc++.h:51,
                 from answer.code:1:
/usr/include/c++/14/bits/stl_algobase.h:257:5: note: candidate: ‘template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)’
  257 |     max(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/14/bits/stl_algobase.h:257:5: note:   template argument deduction/substitution failed:
answer.code:72:22: note:   deduced conflicting types for parameter ‘const _Tp’ (‘long long int’ and ‘int’)
   72 |                 r=max(r,a[i]);
      |                   ~~~^~~~~~~~
/usr/include/c++/14/bits/stl_algobase.h:303:5: note: candidate: ‘template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)’
  303 |     max(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/14/bits/stl_algobase.h:303:5: note:   candidate expects 3 arguments, 2 provided
In file included from /usr/include/c++/14/algorithm:61:
/usr/include/c++/14/bits/stl_algo.h:5705:5: note: candidate: ‘template<class _Tp> constexpr _Tp std::max(initializer_list<_Tp>)’
 5705 |     max(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/14/bits/stl_algo.h:5705:5: note:   candidate expects 1 argument, 2 provided
/usr/include/c++/14/bits/stl_algo.h:5715:5: note: candidate: ‘template<class _Tp, class _Compare> constexpr _Tp std::max(initializer_list<_Tp>, _Compare)’
 5715 |     max(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/14/bits/stl_algo.h:5715:5: note:   template argument deduction/substitution failed:
answer.code:72:22: note:   mismatched types ‘std::initializer_list<_Tp>’ and ‘long long int’
   72 |                 r=max(r,a[i]);
      |                   ~~~^~~~~~~~