1 #include<bits/stdc++.h>

 2 using namespace std;

 3 int n,a[20005];

 4 bool pd(int k){

 5     int mi=a[1],ma=a[1];

 6     if (k<a[n]+a[1])return 0;

 7     for(int i=2;i<=n;i++){

 8         if (k<a[i]+a[i-1])return 0;

 9         int x=max(a[i]-(k-a[i-1]-(a[1]-ma)),0);

10         ma=min(a[i],a[1]-mi);

11         mi=x;

12     }

13     return mi==0;

14 }

15 int main(){

16     scanf("%d",&n);

17     for(int i=1;i<=n;i++)scanf("%d",&a[i]);

18     int l=1,r=300000;

19     while (l<r){

20         int mid=(0LL+l+r>>1);

21         if (pd(mid))r=mid;

22         else l=mid+1;

23     }

24     printf("%d",l);

25 }