import bisect
N=int(input())
A=list(map(int,input().split()))
def f(n,a):
    ret=0
    dp=[10**20]*n
    L=[-1]*n
    for i in range(n):
        to=bisect.bisect_left(dp,a[i])
        dp[to]=a[i]
        L[i]=to
    a=a[::-1]
    dp=[10**20]*n
    for i in range(n):
        to=bisect.bisect_left(dp,a[i])
        dp[to]=a[i]
        ret=max(ret,min(L[n-1-i],to))
    return ret

ans=f(N,A)
for i in range(N):
    A[i]=-A[i]
ans=max(ans,f(N,A))
print(ans)