from bisect import bisect_right



N, *A = list(map(int, open(0).read().split()))



INF = 10 ** 10

dp = [INF] * N

for i in range(N):

    dp[bisect_right(dp, -A[i])] = -A[i]



print((max(i + 1 for i, v in enumerate(dp) if v < INF)))

from bisect import bisect_right



N, *A = list(map(int, open(0).read().split()))



x = [1] * (N + 1)

for i in range(N):

    j = bisect_right(x, -A[i])

    x[j] = -A[i]

print((sum(v != 1 for v in x)))



from bisect import bisect_right

N, *A = list(map(int, open(0).read().split()))
INF = 10**10
dp = [INF] * N
for i in range(N):
    dp[bisect_right(dp, -A[i])] = -A[i]
print((max(i + 1 for i, v in enumerate(dp) if v < INF)))

from bisect import bisect_right

N, *A = list(map(int, open(0).read().split()))
x = [1] * (N + 1)
for i in range(N):
    j = bisect_right(x, -A[i])
    x[j] = -A[i]
print((sum(v != 1 for v in x)))

-INF = 10**10 -dp = [INF] * N +x = [1] * (N + 1) -    dp[bisect_right(dp, -A[i])] = -A[i] -print((max(i + 1 for i, v in enumerate(dp) if v < INF))) +    j = bisect_right(x, -A[i]) +    x[j] = -A[i] +print((sum(v != 1 for v in x)))