#!/usr/bin/env python3

import sys, math, itertools, collections, bisect

input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')

inf = float('inf') ;mod = 10**9+7

mans = inf ;ans = 0 ;count = 0 ;pro = 1



n=int(eval(input()))

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

data=collections.deque()

for i, ai in enumerate(A):

    k=bisect.bisect_left(data,ai)

    if k==0:

        data.appendleft(ai)

    else:

        data[k-1]=ai

print((len(data)))
#!/usr/bin/env python3

import sys, math, itertools, collections, bisect

input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')

inf = float('inf') ;mod = 10**9+7

mans = inf ;ans = 0 ;count = 0 ;pro = 1



n = int(eval(input()))

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

dp = [-inf] * (10**5+10);dp[-1] = inf

for ai in A:

  dp[bisect.bisect_left(dp,ai)-1] = ai

for di in dp:

  if di != -inf:ans += 1

print((ans - 1))
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect

input = lambda: sys.stdin.buffer.readline().rstrip().decode("utf-8")
inf = float("inf")
mod = 10**9 + 7
mans = inf
ans = 0
count = 0
pro = 1
n = int(eval(input()))
A = [int(eval(input())) for i in range(n)]
data = collections.deque()
for i, ai in enumerate(A):
    k = bisect.bisect_left(data, ai)
    if k == 0:
        data.appendleft(ai)
    else:
        data[k - 1] = ai
print((len(data)))

#!/usr/bin/env python3
import sys, math, itertools, collections, bisect

input = lambda: sys.stdin.buffer.readline().rstrip().decode("utf-8")
inf = float("inf")
mod = 10**9 + 7
mans = inf
ans = 0
count = 0
pro = 1
n = int(eval(input()))
A = [int(eval(input())) for i in range(n)]
dp = [-inf] * (10**5 + 10)
dp[-1] = inf
for ai in A:
    dp[bisect.bisect_left(dp, ai) - 1] = ai
for di in dp:
    if di != -inf:
        ans += 1
print((ans - 1))

-data = collections.deque() -for i, ai in enumerate(A): -    k = bisect.bisect_left(data, ai) -    if k == 0: -        data.appendleft(ai) -    else: -        data[k - 1] = ai -print((len(data))) +dp = [-inf] * (10**5 + 10) +dp[-1] = inf +for ai in A: +    dp[bisect.bisect_left(dp, ai) - 1] = ai +for di in dp: +    if di != -inf: +        ans += 1 +print((ans - 1))