# 狭義単調増加部分列

import bisect

from collections import deque



n = int(eval(input()))

A = [int(eval(input())) for _ in range(n)]

que = deque()



for i in range(n):

    if len(que) == 0:

        deque.appendleft(que, A[i])

    else:

        idx = bisect.bisect_left(que, A[i])

        if idx == 0:

            deque.appendleft(que, A[i])

        else:

            que[idx - 1] = A[i]



ans = len(que)

print(ans)

import sys

from collections import deque

from bisect import bisect_left



sys.setrecursionlimit(10 ** 7)

input = sys.stdin.readline

f_inf = float('inf')

mod = 10 ** 9 + 7





def resolve():

    n = int(eval(input()))

    A = list(int(eval(input())) for _ in range(n))



    LIS = deque()

    for i in range(n):

        if len(LIS) == 0:

            LIS.appendleft(A[i])

        else:

            idx = bisect_left(LIS, A[i])

            if idx == 0:

                LIS.appendleft(A[i])

            else:

                LIS[idx - 1] = A[i]

    print((len(LIS)))





if __name__ == '__main__':

    resolve()

# 狭義単調増加部分列
import bisect
from collections import deque

n = int(eval(input()))
A = [int(eval(input())) for _ in range(n)]
que = deque()
for i in range(n):
    if len(que) == 0:
        deque.appendleft(que, A[i])
    else:
        idx = bisect.bisect_left(que, A[i])
        if idx == 0:
            deque.appendleft(que, A[i])
        else:
            que[idx - 1] = A[i]
ans = len(que)
print(ans)

import sys
from collections import deque
from bisect import bisect_left

sys.setrecursionlimit(10**7)
input = sys.stdin.readline
f_inf = float("inf")
mod = 10**9 + 7


def resolve():
    n = int(eval(input()))
    A = list(int(eval(input())) for _ in range(n))
    LIS = deque()
    for i in range(n):
        if len(LIS) == 0:
            LIS.appendleft(A[i])
        else:
            idx = bisect_left(LIS, A[i])
            if idx == 0:
                LIS.appendleft(A[i])
            else:
                LIS[idx - 1] = A[i]
    print((len(LIS)))


if __name__ == "__main__":
    resolve()

-# 狭義単調増加部分列 -import bisect +import sys +from bisect import bisect_left -n = int(eval(input())) -A = [int(eval(input())) for _ in range(n)] -que = deque() -for i in range(n): -    if len(que) == 0: -        deque.appendleft(que, A[i]) -    else: -        idx = bisect.bisect_left(que, A[i]) -        if idx == 0: -            deque.appendleft(que, A[i]) +sys.setrecursionlimit(10**7) +input = sys.stdin.readline +f_inf = float("inf") +mod = 10**9 + 7 + + +def resolve(): +    n = int(eval(input())) +    A = list(int(eval(input())) for _ in range(n)) +    LIS = deque() +    for i in range(n): +        if len(LIS) == 0: +            LIS.appendleft(A[i]) -            que[idx - 1] = A[i] -ans = len(que) -print(ans) +            idx = bisect_left(LIS, A[i]) +            if idx == 0: +                LIS.appendleft(A[i]) +            else: +                LIS[idx - 1] = A[i] +    print((len(LIS))) + + +if __name__ == "__main__": +    resolve()