def LIS(A):

    dp = deque([A[0]])

    for a in A[1:]:

        if a <= dp[0]:

            dp.appendleft(a)

        else:

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

    return len(dp)



##################################################################################################################



import sys

input = sys.stdin.readline

from collections import deque

from bisect import bisect_left



N = int(eval(input()))



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



print((LIS(A)))
def LIS(A):

    dp = [-A[0]]

    for a in A[1:]:

        if -a >= dp[-1]:

            dp.append(-a)

        else:

            dp[bisect_right(dp, -a)] = -a

    return len(dp)



##################################################################################################################



import sys

input = sys.stdin.readline

from bisect import *



N = int(eval(input()))



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



print((LIS(A)))
def LIS(A):
    dp = deque([A[0]])
    for a in A[1:]:
        if a <= dp[0]:
            dp.appendleft(a)
        else:
            dp[bisect_left(dp, a) - 1] = a
    return len(dp)


##################################################################################################################
import sys

input = sys.stdin.readline
from collections import deque
from bisect import bisect_left

N = int(eval(input()))
A = [int(eval(input())) for _ in range(N)]
print((LIS(A)))

def LIS(A):
    dp = [-A[0]]
    for a in A[1:]:
        if -a >= dp[-1]:
            dp.append(-a)
        else:
            dp[bisect_right(dp, -a)] = -a
    return len(dp)


##################################################################################################################
import sys

input = sys.stdin.readline
from bisect import *

N = int(eval(input()))
A = [int(eval(input())) for _ in range(N)]
print((LIS(A)))

-    dp = deque([A[0]]) +    dp = [-A[0]] -        if a <= dp[0]: -            dp.appendleft(a) +        if -a >= dp[-1]: +            dp.append(-a) -            dp[bisect_left(dp, a) - 1] = a +            dp[bisect_right(dp, -a)] = -a -from collections import deque -from bisect import bisect_left +from bisect import *