/* 奇数怎么搞呢 二分到答案怎么judge呢 贪心怎么贪呢 假设贪心方案是 前两个挨着取 后面的能靠前就靠前 这样子似乎保证了ans最min 但是不管贪的对不对 操作起来时间GG 而且 如果真的这样搞 二分出来的答案就没啥用了 如果按二分通常的套路来说 应该是拿二分出的ansi来贪心的溜一遍 看看合不合法 但是一般都有一个值来辅助判断合不合法 显然这个题需要我们自己构造 (emmmm说了一堆废话) 显然一路合法的跑过来就是看看n和1选的重不重合 我们让1选1~a[1] 那就是 最后看看n有没有选1~a[1]里的 这样就找到了最后judge的条件 现在考虑维护这个 "有没有选1~a[1]里" 设为A[i] 往简单了想 设成bool类型 GG 发现维护A[i] 的时候用到了具体的数值 我们改为 "1~a[1]选了多少个" 考虑转移 因为每个元素只与和他挨着的有关系 在跑的时候就只与左边一个有关系 所以两个一组 我们让奇数的尽量选大的 偶数尽量选小的 这样n就和1尽可能错开了 发现搞奇数需要 每个元素除了1-a[1]之外选了几个 记做B[i] 有 偶数:A[i]=min(a[1]-A[i-1],a[i]) B[i]=a[i]-A[i] 奇数:B[i]=min(ansi-a[1]-B[i-1],a[i]) A[i]=a[i]-B[i] */ #include<cstdio> #include<cstring> #include<iostream> #define maxn 100010 using namespace std; int n; long long A[maxn],B[maxn],a[maxn],l,r,ans; int init(){ int x=0,f=1;char s=getchar(); while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();} while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();} return x*f; } bool Judge(long long x){ A[1]=a[1];B[1]=0; for(int i=2;i<=n;i++) if(i&1){ B[i]=min(x-a[1]-B[i-1],a[i]); A[i]=a[i]-B[i]; } else { A[i]=min(a[1]-A[i-1],a[i]); B[i]=a[i]-A[i]; } return A[n]==0; } int main(){ while(1){ scanf("%d",&n); if(n==0)break; for(int i=1;i<=n;i++) a[i]=init(); if(n==1){ printf("%lld ",a[1]);continue; } ans=-1;a[n+1]=a[1]; for(int i=1;i<=n;i++) ans=max(ans,a[i]+a[i+1]); l=ans;r=(long long)1<<40; if(n&1){ while(l<=r){ long long mid=(l+r)/2; if(Judge(mid)){ r=mid-1;ans=mid; } else l=mid+1; } } printf("%lld ",ans); } return 0; }