from bisect import bisect

import sys

n = int(eval(input()))

A = [int(i.rstrip("\n")) for i in sys.stdin.readlines()]

 #?????????i+1??§???????¢??????¨??????????????????????´????????°???????????´?

L = []

def LIS():

    L.append(A[0])

    length = 0

    for i in range(n):

        if L[length] < A[i]:

            length += 1

            L.append(A[i])

        else:

            if A[i] in L: continue

            j = bisect(L, A[i], 0, length) #L????????§?????????A[i]??\?????¨????????????????????????

            L[j] = A[i]

    return length + 1



print((LIS()))
from bisect import bisect_left

import sys



n = int(eval(input()))

A = [int(i.rstrip("\n")) for i in sys.stdin.readlines()]



def LIS():

    L = A[:1]

    for i in A[1:]:

        if L[-1] < i:

            L.append(i)

        else:

            j = bisect_left(L, i)

            L[j] = i

    return len(L)



print((LIS()))
from bisect import bisect
import sys

n = int(eval(input()))
A = [int(i.rstrip("\n")) for i in sys.stdin.readlines()]
# ?????????i+1??§???????¢??????¨??????????????????????´????????°???????????´?
L = []


def LIS():
    L.append(A[0])
    length = 0
    for i in range(n):
        if L[length] < A[i]:
            length += 1
            L.append(A[i])
        else:
            if A[i] in L:
                continue
            j = bisect(
                L, A[i], 0, length
            )  # L????????§?????????A[i]??\?????¨????????????????????????
            L[j] = A[i]
    return length + 1


print((LIS()))

from bisect import bisect_left
import sys

n = int(eval(input()))
A = [int(i.rstrip("\n")) for i in sys.stdin.readlines()]


def LIS():
    L = A[:1]
    for i in A[1:]:
        if L[-1] < i:
            L.append(i)
        else:
            j = bisect_left(L, i)
            L[j] = i
    return len(L)


print((LIS()))

-from bisect import bisect +from bisect import bisect_left -# ?????????i+1??§???????¢??????¨??????????????????????´????????°???????????´? -L = [] -    L.append(A[0]) -    length = 0 -    for i in range(n): -        if L[length] < A[i]: -            length += 1 -            L.append(A[i]) +    L = A[:1] +    for i in A[1:]: +        if L[-1] < i: +            L.append(i) -            if A[i] in L: -                continue -            j = bisect( -                L, A[i], 0, length -            )  # L????????§?????????A[i]??\?????¨???????????????????????? -            L[j] = A[i] -    return length + 1 +            j = bisect_left(L, i) +            L[j] = i +    return len(L)