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 r=_l tmp={M,m1,m2} else: r=max(r,i+1) m1,m2,M=st.query(i,r+1) # これは必ず条件を満たす。 for j in range(r+1,n): m=a[j] if m2==inf and 1: ary=[m1,M,m] ary.sort() if ary[-1]<=ary[0]+ary[1]: r=j m1,m2,M=ary continue else: break if m2<=m<=M: r=j elif Mi,f"error{r,i}" #print(st.query(0,1)) #print(st.query(0,2)) #print(st.query(0,3)) return ans if __name__=='__main__': n=int(input()) a=list(map(int,input().split())) ret1=main1(n,a) print(ret1) exit() ret0=main0(n,a) print(ret0) from random import randint from datetime import datetime if __name__=='__main__': t=datetime.now().timestamp() for _ in range(1): n=randint(10**4,10**4) n=10**5 a=[randint(1,10) for _ in range(n)] #ret0=main0(n,a) ret1=main1(n,a) #if ret0!=ret1: # print(n) # print(*a) # print(ret0,ret1) # break print(datetime.now().timestamp()-t)