JOI 君马上要和妹妹 JOI 子和 JOI 美一起吃小吃。今天的小吃是他们三个人都很喜欢的年轮蛋糕。
年轮蛋糕是像下图一样呈圆筒形的蛋糕。为了把蛋糕分给三个人，JOI 君必须沿着半径方向切 3 刀，从而把蛋糕分成三块。然而，由于年轮蛋糕硬得像实木一样，要让刀切进去并不简单。因此，这个年轮蛋糕上事先准备了 N 个切口，而 JOI 君只能在有切口的位置下刀。切口按顺时针顺序编号为 1到 N，对于 1≤i≤N−1，第 i 个切口和第 i+1个切口之间部分的大小是 Ai。第 N 个切口和第 1个切口之间部分的大小是 AN 。
图 1：一个年轮蛋糕的例子，N=6,A1=1,A2=5,A3=4,A4=5,A5=2,A6=4
妹控的 JOI 君在把蛋糕切成 3 块之后，自己选走最小的一块吃掉，把剩下两块分给两个妹妹。而另一方面，JOI 君太喜欢年轮蛋糕了，只要能吃到的时候就会想吃很多很多。试求：最小块的大小不超过多少。
样例说明 1
图 2：从第 1,3,5个切口下刀时是最优解（即图中粗实线位置）。
这道题用二分+二分。我们知道分一个蛋糕需要切三刀，第一刀枚举O(n),第二刀二分logN,第三刀二分logN，一共O(nlogn^2),可以过。
第一、二刀会把最小的一块给切走，然后留下一大块。
然后用第三刀切这一大块，如果这两块切完都比刚才切走的小，说明这一大块无论怎么切都切不出符合的结果，所以开始的一块切大了，第二刀往小切
如果前面一块小于刚切走的，说明第三刀要往后切；
如果后面一块小了，就往前切；
如果两块都可以，说明这种切法可行，第二刀尝试往更大的切。
注意所有数组下表的处理。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <stack>
#define in(a) a=read()
#define MAXN 200020
#define REP(i,k,n) for(long long i=k;i<=n;i++)
using namespace std;
inline long long read(){
long long x=,f=;
char ch=getchar();
for(;!isdigit(ch);ch=getchar())
if(ch=='-')
f=-;
for(;isdigit(ch);ch=getchar())
x=x*+ch-'';
return x*f;
}
long long n;
long long ans;
long long a[MAXN],s[MAXN];
inline bool check(long long i,long long k){
long long sum=s[i+k-]-s[i-];
long long loc=i+k-;
long long left=,right=n;
while(right-left>){
long long mid=(right+left)/;
if(s[loc+mid]-s[loc]<sum && s[i+n-]-s[loc+mid]<sum) return ;
if(s[loc+mid]-s[loc]<sum) left=mid;
if(s[i+n-]-s[loc+mid]<sum) right=mid;
if(s[loc+mid]-s[loc]>=sum && s[i+n-]-s[loc+mid]>=sum) return ;
}
return ;
}
int main(){
in(n);
REP(i,,n){
in(a[i]);
a[i+n]=a[i];
s[i]=s[i-]+a[i];
}
REP(i,,n)
s[i+n]=s[i+n-]+a[i+n];
REP(i,,n){
long long left=,right=n;
while(right-left>){
long long mid=(left+right)/;
if(check(i,mid)) left=mid;
else right=mid;
}
ans=max(s[i+left-]-s[i-],ans);
}
cout<<ans;
return ;
}