from bisect import bisect_left
N = int(input())
A = list(map(int, input().split()))
def LIS(A,N):
    lis = []
    ans = [0]*N
    for i in range(N):
        ind = bisect_left(lis,A[i])
        ans[i] = ind
        if ind == len(lis):
            lis.append(A[i])
        else:
            lis[ind] = A[i]
    return ans
def kadomatsu(A,N):
    lis1 = LIS(A,N)
    lis2 = LIS(A[::-1],N)[::-1]
    ans = 0
    for i in range(N):
        ans = max(ans, min(lis1[i],lis2[i]))
    return ans
a = kadomatsu(A,N)
b = kadomatsu(list(map(lambda x:-x,A)),N)
print(max(a,b))