# -*- coding: utf-8 -*-



import sys

from collections import deque

from bisect import bisect_left



def input(): return sys.stdin.readline().strip()

def list2d(a, b, c): return [[c] * b for i in range(a)]

def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]

def ceil(x, y=1): return int(-(-x // y))

def INT(): return int(eval(input()))

def MAP(): return list(map(int, input().split()))

def LIST(): return list(map(int, input().split()))

def Yes(): print('Yes')

def No(): print('No')

def YES(): print('YES')

def NO(): print('NO')

sys.setrecursionlimit(10 ** 9)

INF = float('inf')

MOD = 10 ** 9 + 7



def LDS(A: list):

    L = deque([A[0]])

    for a in A[1:]:

        if a <= L[0]:

            # Lの先頭よりaが小さければ減少部分列を延長する(今回は広義(=を含む))

            L.appendleft(a)

        else:

            # そうでなければ、「a以上の最小要素の手前」をaにする

            # 該当位置は、二分探索で特定できる

            L[bisect_left(L, a)-1] = a

    return len(L)



N=INT()

A=[INT() for i in range(N)]



print((LDS(A)))

# -*- coding: utf-8 -*-



import sys

from bisect import bisect_right



def input(): return sys.stdin.readline().strip()

def list2d(a, b, c): return [[c] * b for i in range(a)]

def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]

def ceil(x, y=1): return int(-(-x // y))

def INT(): return int(eval(input()))

def MAP(): return list(map(int, input().split()))

def LIST(): return list(map(int, input().split()))

def Yes(): print('Yes')

def No(): print('No')

def YES(): print('YES')

def NO(): print('NO')

sys.setrecursionlimit(10 ** 9)

INF = float('inf')

MOD = 10 ** 9 + 7



N=INT()

A=[INT() for i in range(N)]



def LIS(A: list):

    L = [A[0]]

    for a in A[1:]:

        if a >= L[-1]:

            # aがLの末尾以上なら増加部分列を延長する(今回は広義(=を含む))

            L.append(a)

        else:

            # そうでなければ、「a以下の最大要素の次」をaにする

            # 該当位置は、二分探索で特定できる

            L[bisect_right(L, a)] = a

    return len(L)



# 後ろからLIS

print((LIS(A[::-1])))

# -*- coding: utf-8 -*-
import sys
from collections import deque
from bisect import bisect_left


def input():
    return sys.stdin.readline().strip()


def list2d(a, b, c):
    return [[c] * b for i in range(a)]


def list3d(a, b, c, d):
    return [[[d] * c for j in range(b)] for i in range(a)]


def ceil(x, y=1):
    return int(-(-x // y))


def INT():
    return int(eval(input()))


def MAP():
    return list(map(int, input().split()))


def LIST():
    return list(map(int, input().split()))


def Yes():
    print("Yes")


def No():
    print("No")


def YES():
    print("YES")


def NO():
    print("NO")


sys.setrecursionlimit(10**9)
INF = float("inf")
MOD = 10**9 + 7


def LDS(A: list):
    L = deque([A[0]])
    for a in A[1:]:
        if a <= L[0]:
            # Lの先頭よりaが小さければ減少部分列を延長する(今回は広義(=を含む))
            L.appendleft(a)
        else:
            # そうでなければ、「a以上の最小要素の手前」をaにする
            # 該当位置は、二分探索で特定できる
            L[bisect_left(L, a) - 1] = a
    return len(L)


N = INT()
A = [INT() for i in range(N)]
print((LDS(A)))

# -*- coding: utf-8 -*-
import sys
from bisect import bisect_right


def input():
    return sys.stdin.readline().strip()


def list2d(a, b, c):
    return [[c] * b for i in range(a)]


def list3d(a, b, c, d):
    return [[[d] * c for j in range(b)] for i in range(a)]


def ceil(x, y=1):
    return int(-(-x // y))


def INT():
    return int(eval(input()))


def MAP():
    return list(map(int, input().split()))


def LIST():
    return list(map(int, input().split()))


def Yes():
    print("Yes")


def No():
    print("No")


def YES():
    print("YES")


def NO():
    print("NO")


sys.setrecursionlimit(10**9)
INF = float("inf")
MOD = 10**9 + 7
N = INT()
A = [INT() for i in range(N)]


def LIS(A: list):
    L = [A[0]]
    for a in A[1:]:
        if a >= L[-1]:
            # aがLの末尾以上なら増加部分列を延長する(今回は広義(=を含む))
            L.append(a)
        else:
            # そうでなければ、「a以下の最大要素の次」をaにする
            # 該当位置は、二分探索で特定できる
            L[bisect_right(L, a)] = a
    return len(L)


# 後ろからLIS
print((LIS(A[::-1])))

-from collections import deque -from bisect import bisect_left +from bisect import bisect_right +N = INT() +A = [INT() for i in range(N)] -def LDS(A: list): -    L = deque([A[0]]) +def LIS(A: list): +    L = [A[0]] -        if a <= L[0]: -            # Lの先頭よりaが小さければ減少部分列を延長する(今回は広義(=を含む)) -            L.appendleft(a) +        if a >= L[-1]: +            # aがLの末尾以上なら増加部分列を延長する(今回は広義(=を含む)) +            L.append(a) -            # そうでなければ、「a以上の最小要素の手前」をaにする +            # そうでなければ、「a以下の最大要素の次」をaにする -            L[bisect_left(L, a) - 1] = a +            L[bisect_right(L, a)] = a -N = INT() -A = [INT() for i in range(N)] -print((LDS(A))) +# 後ろからLIS +print((LIS(A[::-1])))