class Segment_Tree(): """ このプログラム内は1-index """ def __init__(self,L,calc,unit): """calcを演算とするリストLのSegment Treeを作成 calc:演算(2変数関数,モノイド) unit:モノイドcalcの単位元 (xe=ex=xを満たすe) """ self.calc=calc self.unit=unit N=len(L) d=max(1,(N-1).bit_length()) k=1<<d self.data=[unit]*k+L+[unit]*(k-len(L)) self.N=k self.depth=d for i in range(k-1,0,-1): self.data[i]=calc(self.data[i<<1],self.data[i<<1|1]) def get(self,k,index=1): """第k要素を取得 """ assert 0<=k-index<self.N,"添字が範囲外" return self.data[k-index+self.N] def update(self,k,x,index=1): """第k要素をxに変え,更新を行う. k:数列の要素 x:更新後の値 """ assert 0<=k-index<self.N,"添字が範囲外" m=(k-index)+self.N self.data[m]=x while m>1: m>>=1 self.data[m]=self.calc(self.data[m<<1],self.data[m<<1|1]) def product(self,From,To,index=1,left_closed=True,right_closed=True): L=(From-index)+self.N+(not left_closed) R=(To-index)+self.N+(right_closed) vL=self.unit vR=self.unit while L<R: if L&1: vL=self.calc(vL,self.data[L]) L+=1 if R&1: R-=1 vR=self.calc(self.data[R],vR) L>>=1 R>>=1 return self.calc(vL,vR) def all_product(self): return self.data[1] def max_right(self,l,r,cond,index=0): """以下の2つをともに満たすxの1つを返す.\n (1) r=l or cond(data[l]*data[l+1]*...*d[r-1]):True (2) r=x or cond(data[l]*data[l+1]*...*data[r]):False ※fが単調減少の時,cond(data[l]*...*data[r-1])を満たす最大のrとなる. cond:関数(引数が同じならば結果も同じ) cond(unit):True 0<=l<=r<=n """ l-=index assert 0<=l<=r<=self.num,"添字が範囲外" assert cond(self.unit),"単位元が条件を満たさない." if l==r: return r+index l+=(self.num-1) sm=self.unit calc=self.calc while True: while l%2: l=(l-1)>>1 if not cond(calc(sm,self.data[l])): while l<self.num-1: l=2*l+1 if cond(calc(sm,self.data[l])): sm=calc(sm,self.data[l]) l+=1 return min(l-(self.num-1)+index,r) sm=calc(sm,self.data[l]) l+=1 m=l+1 if not (m&(-m) !=m): break return r+index #================================================ N=int(input()) A=list(map(int,input().split())) B=sorted(A) inf=float("inf") D={x:i for i,x in enumerate(B)} S=Segment_Tree([inf]*N,min, inf) T=Segment_Tree(B.copy(),min, inf) X=inf for i in range(N): m=D[A[i]] T.update(m, inf,0) if m>0: x=S.product(0,m-1,0) y=T.product(0,m-1,0) if x<A[i] and y<A[i]: X=min(X,x+y+A[i]) if m<N-1: x=S.product(m+1,N-1,0) y=T.product(m+1,N-1,0) if x>A[i] and y>A[i]: X=min(X,x+y+A[i]) S.update(m,A[i],0) if X==inf: print(-1) else: print(X)