from bisect import * def solve1182(): print('kaage') def solve1183(): N=int(input()) A=list(map(int,input().split())) B=list(map(int,input().split())) for i in range(N): A[i]^=B[i] P=A[0] for i in range(N-1): if A[i]==0 and A[i+1]==1: P+=1 print(P) def solve1184(): N,L=map(int,input().split()) print(pow(2,(N+L-1)//L,998244353)-1) def solve1185(): N=int(input()) i=0 r=(1<<20) P=-4 j=0 k=0 while(i<r): j=i k=0 for l in range(10): k+=((j&3)*3*(10**l)) j>>=2 if N>=k: P+=1 else: break i+=1 for i in range(10): for j in range(10): if i%3 and j%3 and (i+j)%3==0: if i*10+j<=N: P+=1 print(P) def solve1186(): N,M=map(int,input().split()) if N==1: print(1) exit() mod=998244353 DP=[0]*(M+1) DP[0]=1 for i in range(M): DP[i+1]=(DP[i]+DP[i+1])%mod if i+N<=M: DP[i+N]=DP[i] print(DP[-1]) def solve1187(): L,R=0,1000 X=0 S=0 T=0 while R-L>1: X=(L+R)//2 print('?',X) S=input() print('?',X+1) T=input() if T=='out' and S=='out': R=X elif S=='safe' and T=='out': L=X else: L=X+1 print('?',R) if input()=='out': print('!',L) else: print('!',R) def solve1188(): def LIS(A): N=len(A) R=[] INF=10**17 DP=[INF]*(N+1) DP[0]=-INF for i in range(N): R.append(bisect_left(DP,A[i])) DP[R[i]]=A[i] return R N=int(input()) A=list(map(int,input().split())) B=A[::-1] C=[-A[i] for i in range(N)] D=C[::-1] A=LIS(A) B=LIS(B) C=LIS(C) D=LIS(D) print(max([max(min(A[i],B[-i-1]),min(C[i],D[-1-i])) for i in range(N)])-1) solve1188()