class SegmentTree(): def __init__(self,size,f=lambda x,y:x+y,default=0): self.size=pow(2,(size-1).bit_length()) self.f=f self.default=default self.data=[default]*(self.size*2) def update(self,i,x): i+=self.size self.data[i]=x while i: i>>=1 self.data[i]=self.f(self.data[i*2],self.data[i*2+1]) # 区間[l,r)へのクエリ def query(self,l,r): l,r=l+self.size,r+self.size lret,rret=self.default,self.default while l>=1 r>>=1 return self.f(lret,rret) def get(self,i): return self.data[self.size+i] def add(self,i,x): self.update(i,self.get(i)+x) def main0(n,a): inf=10**10 def f(x,y): ary=[] xidx,yidx=0,0 while len(ary)<2: if x[xidx]1: x=(l+r)//2 m1,m2,M=st.query(i,x+1) if M<=m1+m2: l,r=x,r else: l,r=l,x ans+=(l-i) return ans class SegmentTree(): def __init__(self,size,f=lambda x,y:x+y,default=0): self.size=pow(2,(size-1).bit_length()) self.f=f self.default=default self.data=[default]*(self.size*2) def update(self,i,x): i+=self.size self.data[i]=x while i: i>>=1 self.data[i]=self.f(self.data[i*2],self.data[i*2+1]) # 区間[l,r)へのクエリ def query(self,l,r): l,r=l+self.size,r+self.size lret,rret=self.default,self.default while l>=1 r>>=1 return self.f(lret,rret) def get(self,i): return self.data[self.size+i] def add(self,i,x): self.update(i,self.get(i)+x) def main1(n,a): inf=10**10 def f(x,y): ary=[] xidx,yidx=0,0 while len(ary)<2: if x[xidx]1: x=(l+r)//2 m1,m2,M=st.query(i,x+1) if M<=m1+m2: l,r=x,r else: l,r=l,x ans+=(l-i) tmp={M,m1,m2} return ans if __name__=='__main__': n=int(input()) a=list(map(int,input().split())) #ret0=main0(n,a) ret1=main1(n,a) #print(ret0) print(ret1)