# https://atcoder.jp/contests/abc134/tasks/abc134_e　



from bisect import bisect_left

from collections import *



N = int(eval(input()))



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



LIS = deque([A[0]])

cnt = 0



for a in A[1:]:

    if a <= LIS[0]:

        LIS.appendleft(a)

    else:

        ind = bisect_left(LIS, a) -1

        LIS[ind] = a



print((len(LIS)))
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)))
# https://atcoder.jp/contests/abc134/tasks/abc134_e
from bisect import bisect_left
from collections import *

N = int(eval(input()))
A = [int(eval(input())) for _ in range(N)]
LIS = deque([A[0]])
cnt = 0
for a in A[1:]:
    if a <= LIS[0]:
        LIS.appendleft(a)
    else:
        ind = bisect_left(LIS, a) - 1
        LIS[ind] = a
print((len(LIS)))

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)))

-# https://atcoder.jp/contests/abc134/tasks/abc134_e +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 collections import * -LIS = deque([A[0]]) -cnt = 0 -for a in A[1:]: -    if a <= LIS[0]: -        LIS.appendleft(a) -    else: -        ind = bisect_left(LIS, a) - 1 -        LIS[ind] = a -print((len(LIS))) +print((LIS(A)))