分奇偶讨论;
#include <cstdio> #include <iostream> #include <cstring> #include <algorithm> #include <cmath> #include <vector> #include <map> using namespace std; typedef long long LL; const int maxn = 100000+10; int n,a[maxn],le[maxn],ri[maxn]; int Judge(int x){ le[1] = a[1]; ri[1] = 0; int p = a[1]; for(int i=2;i<=n;i++){ if(i&1){ ri[i]=min(x-p-ri[i-1],a[i]); le[i]=a[i]-ri[i]; } else { le[i]=min(p-le[i-1],a[i]); ri[i]=a[i]-le[i]; } } return le[n]==0; } int main() { while(scanf("%d",&n)==1 && n){ int x = 0; for(int i=1;i<=n;i++){ scanf("%d",&a[i]); } for(int i=1;i<=n;i++){ int next = i==n ? 1 : i+1; x=max(x,a[i]+a[next]); } if(!(n&1)){ printf("%d\n",x); continue; } else { if(n==1){ printf("%d\n",a[1]); continue; } int y = 500000; while(x<y){ int m = x+ (y-x)/2; if(Judge(m)) y=m; else x=m+1; } printf("%d\n",x); } } return 0; }