CodeEff/ECCO huggingface dataset:
# Original solution
n = int(eval(input()))
a_ls = []
for i in range(n):
    a_ls.append(int(eval(input())))
cnt = 0
while len(a_ls) > 0:
    cnt += 1
    L_ls = [a_ls[0]]
    for a in a_ls[1:]:
        if L_ls[-1] < a:
            L_ls.append(a)
    for a in L_ls:
        a_ls.remove(a)
print(cnt)

# Optimized solution
import bisect
n = int(eval(input()))
a_ls = []
for i in range(n):
    a_ls.append(-int(eval(input())))
L_ls = [a_ls[0]]
for a in a_ls[1:]:
    if L_ls[-1] <= a:
        L_ls.append(a)
    else:
        L_ls[bisect.bisect_right(L_ls, a)] = a
print((len(L_ls)))
# Original solution
#!/usr/bin/env python3

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7

n = int(eval(input()))
a = [int(eval(input())) for _ in range(n)]
dp = [float('inf')]*n
for i in range(n):
    x = bisect.bisect_right(dp,-a[i])
    dp[x] = -a[i]
c = dp.count(float('inf'))
print((n-c))


# Optimized solution
#!/usr/bin/env python3
#ABC134 E

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
a = [I() for _ in range(n)]

x = [float('inf') for _ in range(n)]
for i in range(n)[::-1]:
    r = bisect.bisect_right(x,a[i])
    x[r] = a[i]
cnt = x.count(float('inf'))
print((n-cnt))
# Original solution
#!/usr/bin/env python3
#ABC134 E

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
a = [I() for _ in range(n)]

x = [float('inf') for _ in range(n)]
for i in range(n)[::-1]:
    r = bisect.bisect_right(x,a[i])
    x[r] = a[i]
cnt = x.count(float('inf'))
print((n-cnt))


# Optimized solution
#!/usr/bin/env python3
import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

def main():
  n = I()
  a = [I() for _ in range(n)]
  dp = [inf]*n
  for i in range(n):
    r = br(dp,-a[i])
    dp[r] = -a[i]
  print((n-dp.count(inf)))
  return

if __name__ == '__main__':
  main()
# Original solution
#!/usr/bin/env python3
import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

def main():
  n = I()
  a = [I() for _ in range(n)]
  dp = [inf]*n
  for i in range(n):
    r = br(dp,-a[i])
    dp[r] = -a[i]
  print((n-dp.count(inf)))
  return

if __name__ == '__main__':
  main()


# Optimized solution
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
a = [I() for _ in range(n)]
dp = [10**10]*(n)
for i in range(n):
    r = br(dp, -a[i])
    dp[r] = -a[i]
print((n - dp.count(10**10)))
# Original solution
N = int(eval(input()))
A = list(int(eval(input()))for i in range(N))
H = [A[0]]
for i in range(1,N):
    if A[i] <= H[-1]:
        H.append(A[i])
    else:
        l,r =0,len(H)
        while l != r :
            if H[(l+r)//2]>=A[i]:
                l = (l+r)//2+1
            else:
                r = (l+r)//2
        H[l] = A[i]
print((len(H)))


# Optimized solution
import bisect
N = int(eval(input()))
A = [int(eval(input()))for i in range(N)]
m = [-A[0]]
ans = 1
for i in A[1:]:
    p = bisect.bisect_left(m,-i+1)
    if p == ans:
        ans += 1
        m.append(-i)
    else:
        m[p] = -i
print(ans)
# Original solution
import sys
input = sys.stdin.readline

N = int(eval(input()))
l = [[int(eval(input()))]]

for i in range(N-1):
  ai = int(eval(input()))
  flag = False
  for m in l:
    if max(m) < ai:
      m.append(ai)
      flag = True
      break
  if flag == False:
    l.append([ai])
    
print((len(l)))

# Optimized solution
import sys
input = sys.stdin.readline
from bisect import bisect_right

N = int(eval(input()))
l = [-int(eval(input()))]

for i in range(N-1):
  ai = -int(eval(input()))
# 各色の最大値がlの要素になるようにリストを拡大させていく
  if l[-1] <= ai:
    l.append(ai)
  else:
    b = bisect_right(l, ai)
    l[b] = ai
    
print((len(l)))
# Original solution
from bisect import bisect_left, bisect_right
n = int(eval(input()))
INF = 1010101010
dp = [INF] * n
a = [int(eval(input())) for _ in range(n)]
a.reverse()
for i in a:
    dp[bisect_right(dp, i)] = i
print((bisect_left(dp, INF)))

# Optimized solution
#「与えられた数列の、広義単調減少列の長さの最大値 L」
from bisect import bisect_left, bisect_right
n = int(eval(input()))
INF = 1010101010
dp = [INF] * n
a = [int(eval(input())) for _ in range(n)]
a.reverse()
for i in a:
    dp[bisect_right(dp, i)] = i
print((bisect_left(dp, INF)))
# Original solution
n=int(eval(input()))
a=[-int(eval(input()))]
l=1
for i in range(1,n):
  b=-int(eval(input()))
  if a[-1]>b:
    if a[0]>b:a[0]=b;continue
    ok=l
    ng=0
    c=ok//2
    while ng+1<ok:
      if b<a[c]:ok=c
      else:ng=c
    a[ok]=b
  else:a.append(b);l+=1
print(l)

# Optimized solution
import bisect
n=int(eval(input()))
x=[int(eval(input()))for _ in range(n)]
a=[-x[0]]
l=1
for i in range(1,n):
  b=-x[i]
  if a[-1]>b:
    if a[0]>b:a[0]=b;continue
    a[bisect.bisect_right(a,b)]=b
  else:a.append(b);l+=1
print(l)
# Original solution
a=int(eval(input()))
b=[int(eval(input())) for i in range(a)]
c=[]
for i in range(a):
  d=0
  for j in range(len(c)):
    if b[i]>c[j]:
      d=1
      c[j]=b[i]
      break
  if d==0:
    e=b[i]
    c.append(e)    
print((len(c)))

# Optimized solution
a=int(eval(input()))
b=[int(eval(input())) for i in range(a)]
LIS = [b[0]]
for i in range(1,len(b)):
  if b[i] <= LIS[-1]:
    LIS.append(b[i])
  else:
    lo=0
    hi=len(LIS)
    while lo < hi:
      mid=(lo+hi)//2
      if b[i]>LIS[mid]:
        hi =mid
      else:
        lo=mid+1  
    LIS[lo] = b[i]
print((len(LIS)))
# Original solution
import bisect

n = int(eval(input()))
a = [int(eval(input())) for _ in range(n)]


b = []

for ai in a:
    if len(b) == 0:
        b.append(ai)
    else:
        if ai <= b[0]:
            b = [ai] + b
        else:
            index = bisect.bisect_left(b, ai)
            b[index-1] = ai

print((len(b)))


# Optimized solution
n = int(eval(input()))
a = [int(eval(input())) for _ in range(n)]


b = []

for ai in a:
    if len(b) == 0:
        b.append(ai)
    else:
        if ai <= b[-1]:
            b.append(ai)
        else:
            l = -1
            r = len(b)
            mid = (l + r) // 2
            while (r - l > 1):
                mid = (l + r) // 2
                if b[mid] >= ai:
                    l = mid
                else:
                    r = mid
            b[r] = ai

print((len(b)))
# Original solution
from bisect import bisect_left
from collections import deque

n = int(eval(input()))
ans = []
ans.append(int(eval(input())))

for i in range(n-1):
  
  temp = int(eval(input()))
  #print("ans " +  str(ans) + " temp " + str(temp))
  if temp <= ans[0]:
    d = deque(ans)
    d.appendleft(temp)
    ans = list(d)
  else:
    loc = bisect_left(ans, temp)
    ans[loc-1]=temp
#print(ans)
print((len(ans)))
  

# Optimized solution
from bisect import bisect_left
from collections import deque

n = int(eval(input()))
ans = []
ans.append(int(eval(input())))
ans = deque(ans)
for i in range(n-1):  
  temp = int(eval(input()))
  #print("ans " +  str(ans) + " temp " + str(temp))
  if temp <= ans[0]:
    #d = deque(ans)
    #d.appendleft(temp)
    #ans = list(d)
    ans.appendleft(temp)
  else:
    ans[bisect_left(ans, temp)-1]=temp
#print(ans)
print((len(ans)))
# Original solution
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(eval(input()))
def MAP(): return list(map(int, input().split()))
def LIST(): return list(map(int, input().split()))
def TUPLE(): return tuple(map(int, input().split()))
def ZIP(n): return list(zip(*(MAP() for _ in range(n))))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 
#mod = 998244353
from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

N = INT()
A = [INT() for _ in range(N)]

color_max = deque([])
cnt = 0

for a in A:
	idx = bisect_left(color_max, a)
	if idx == 0:
		color_max.appendleft(a) 
		cnt += 1
	else:
		color_max[idx-1] = a

print(cnt)

# Optimized solution
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(eval(input()))
def MAP(): return list(map(int, input().split()))
def LIST(): return list(map(int, input().split()))
def TUPLE(): return tuple(map(int, input().split()))
def ZIP(n): return list(zip(*(MAP() for _ in range(n))))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 
#mod = 998244353
from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

N = INT()
A = [INT() for _ in range(N)]

seq = A[::-1]
LIS = [seq[0]]
for i in range(1, N):
	if LIS[-1] <= seq[i]:
		LIS.append(seq[i])
	else:
		LIS[bisect(LIS, seq[i])] = seq[i]

print((len(LIS)))
# Original solution
from bisect import bisect_left, bisect_right

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


dp = [float('inf')] * (N+1)
for A in reversed(As):
    i = bisect_right(dp, A)
    dp[i] = A

print((dp.index(float('inf'))))


# Optimized solution
from bisect import bisect_left, bisect_right
import sys
input = sys.stdin.readline

INF = float('inf')

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

def getLenLNDS(As):
    dp = [-INF]
    for A in As:
        if dp[-1] <= A:
            dp.append(A)
        else:
            i = bisect_right(dp, A)
            dp[i] = A
    return len(dp)-1

ans = getLenLNDS(As)

print(ans)
# Original solution
import bisect

n = int(eval(input()))
ans_head=[-1]

a_list=[]
for i in range(n):
  a_list.append(int(eval(input())))

for i in range(n):
  a=a_list[i]
  if ans_head[0]>=a:
    ans_head=[a]+ans_head
  else:
    insert_index = bisect.bisect_left(ans_head,a)
    ans_head[insert_index-1]=a

  #print(ans_head)
print((len(ans_head)))


# Optimized solution
import bisect
n=int(eval(input()))
A=[]
for i in range(n):
  A.append(int(eval(input())))
Ans=[A[-1]]
for i in reversed(list(range(n-1))):
  a=A[i]
  if a>=Ans[-1]:
    Ans.append(a)
  else:

    Ans[bisect.bisect_right(Ans,a)]=a

print((len(Ans)))
# Original solution
from bisect import bisect_left,bisect

n = int(eval(input()))
p = [[int(eval(input()))]]
for i in range(n-1):
    now = int(eval(input()))
    if now > p[0][-1]:
        p[0].append(now)
    else:
        t = bisect_left(p[0],now)
        k = p[0][t]
        p[0][t] = now
        cou = 1
        while True:
            if cou <= len(p) - 1:
                if k > p[cou][-1]:
                    p[cou].append(k)
                    break
                else:
                    t = bisect_left(p[cou],k)
                    nextk = p[cou][t]
                    p[cou][t] = k
                    k = nextk
                    cou += 1
            elif cou == len(p):
                p.append([k])
                break
print((len(p)))

# Optimized solution
from bisect import bisect_left,bisect
 
n = int(eval(input()))
p = [-1*int(eval(input()))]
for i in range(n-1):
    now = -1*int(eval(input()))
    if now >= p[-1]:
        p.append(now)
    else:
        p[bisect(p,now)] = now
print((len(p)))
# Original solution
n=int(eval(input()))
a=[-1]
for _ in range(n):
    x=int(eval(input()))
    if a[-1]>=x:
        a.append(x)
    else:
        for i in range(len(a)):
            if a[i]<x:
                a[i]=x
                break
print((len(a)))

# Optimized solution
import bisect
n=int(eval(input()))
h=[]
for i in range(n):
  a=int(eval(input()))
  if len(h)==0:
    h.append(-1*a)
  elif (-1)*a>=h[-1]:
    h.append(-1*a)
  else:
    index=bisect.bisect_right(h,-1*a)
    h[index]=-1*a
print((len(h)))
# Original solution
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, A):
    
    L = [A.pop(0)]
    ma = L[0]
    for a in A:
        if ma >= a:
            ma = a
            L.append(ma)
            continue
        for i, l in enumerate(L):
            if l < a:
                L[i] = a
                if l == ma:
                    ma = L[-1]
                break
        else:
            L.append(a)
    return len(L)


def main():
    N = read_int()
    A = [read_int() for _ in range(N)]
    print(slv(N, A))

    # N = 10**5
    # A = [random.randint(1, 10**9) for _ in range(N//2)]
    # A.sort()
    # A.reverse()
    # A += [random.randint(1, 10**9) for _ in range(N//2)]
    # print(slv(N, A))


if __name__ == '__main__':
    main()


# Optimized solution
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


# @mt
def slv(N, A):
    
    L = [-A.pop(0)]
    ma = L[0]
    for a in A:
        if ma <= -a:
            ma = -a
            L.append(ma)
            continue
        i = bisect.bisect_right(L, -a)
        L[i] = -a
        ma = L[-1]
    return len(L)



def main():
    N = read_int()
    A = [read_int() for _ in range(N)]
    print(slv(N, A))


if __name__ == '__main__':
    main()
# Original solution
import bisect
from collections import deque
N = int(eval(input()))
A = [int(eval(input())) for _ in range(N)]
c = deque()
c.append(A[0])
for i in range(1, N):
    j = bisect.bisect_right(c, A[i]-1)
    if j == 0:
        c.appendleft(A[i])
    else:
        c[j-1] = A[i]
print((len(c)))


# Optimized solution
import bisect
from collections import deque
N = int(eval(input()))
A = [int(eval(input())) for _ in range(N)]
c = deque()
c.append(A[0])
for i in range(1, N):
    j = bisect.bisect_left(c, A[i])
    if j == 0:
        c.appendleft(A[i])
    else:
        c[j-1] = A[i]
print((len(c)))
# Original solution
import bisect


def main():
  x = [int(eval(input())) for _ in range(int(eval(input())))]
  c = [x[-1]]

  for i in range(len(x) - 2, -1, -1):
    j = bisect.bisect(c, x[i])

    if j == len(c):
      c.append(x[i])
    else:
      c = c[:j] + c[j + 1:]
      bisect.insort(c, x[i])

  print((len(c)))


if __name__ == '__main__':
  main()


# Optimized solution
import bisect


def main():
  x = [int(eval(input())) for _ in range(int(eval(input())))]
  c = [x[-1]]

  for i in range(len(x) - 2, -1, -1):
    j = bisect.bisect(c, x[i])

    if j == len(c):
      c.append(x[i])
    else:
      c[j] = x[i]

  print((len(c)))


if __name__ == '__main__':
  main()
# Original solution
from bisect import bisect_left

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

t = [A[0]]
for a in A[1:]:
    i = bisect_left(t, a) - 1
    if i == -1:
        t = [a] + t
    else:
        t[i] = a
        t.sort()
print((len(t)))


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

t = [A[0]]
for a in A[1:]:
    if t[-1] >= a:
        t.append(a)
        continue
    ok = len(t) - 1
    ng = -1
    while ok - ng > 1:
        m = (ok + ng) // 2
        if t[m] < a:
            ok = m
        else:
            ng = m
    t[ok] = a
print((len(t)))
# Original solution
import sys
from bisect import *

input=sys.stdin.readline

def f(n):
    r = []
    for _ in range(n):
        a = int(eval(input()))
        if not r:
            r.append(a)
            continue
        i = bisect_left(r, a)
        if i:
            r[i-1]=a
        else:
            r = [a] + r
    print((len(r)))

n = int(eval(input()))
f(n)


# Optimized solution
import sys
from bisect import *

input=sys.stdin.readline

def f(n):
    mi=-1
    r = [inf]*n
    for _ in range(n):
        a = -int(eval(input()))
        i = bisect_right(r, a)
        r[i]=a
        if i>mi:
            mi=i
    print((mi+1))

n = int(eval(input()))
inf=10**10
f(n)
# Original solution
# 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)))

# Optimized solution
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)))
# Original solution
#

#

import itertools
from collections import Counter
from collections import defaultdict
from collections import deque
import bisect
from heapq import heappush, heappop

def main():
    n = int(eval(input()))
    al = [int(eval(input())) for _ in range(n)]

    lsbs = []
    for a in al:
        if len(lsbs) == 0:
            lsbs.append([a])
        else:
            added = False
            for lsb in lsbs:
                if lsb[-1] < a:
                    lsb.append(a)
                    added = True
                    break
            if not added:
                lsbs.append([a])
    print((len(lsbs)))


if __name__ == '__main__':
    main()


# Optimized solution
#

#

import itertools
from collections import Counter
from collections import defaultdict
from collections import deque
import bisect
from heapq import heappush, heappop

def main():
    n = int(eval(input()))
    al = [int(eval(input())) for _ in range(n)]

    lsbs = deque()
    for a in al:
        pos = bisect.bisect_left(lsbs, a)
        if pos == 0:
            lsbs.appendleft(a)
        else:
            if pos == len(lsbs):
                lsbs[-1] = a
            else:
                lsbs[pos-1] = a
        # print(lsbs)
    print((len(lsbs)))


if __name__ == '__main__':
    main()
# Original solution
N = int(eval(input()))
A = [int(eval(input())) for _ in [0]*N]
B = [A[0]]
for a in A[1:]:
    for i,b in enumerate(B):
        if b<a:
            B[i] = a
            break
    else:
        B.append(a)
print((len(B)))

# Optimized solution
N = int(eval(input()))
A = [int(eval(input())) for _ in [0]*N]
B = [A[0]]
ans = 1

for a in A[1:]:
    l = 0
    r = ans - 1
    if B[0]<a:r=0
    while l+1<r:
        i = (l+r)//2
        if B[i] < a:
            r = i
        else:
            l = i
    if B[r]<a:B[r] = a
    else:
        B.append(a)
        ans += 1
print(ans)
# Original solution
import bisect

N = int(eval(input()))
A = []

a = int(eval(input()))

val = [-a]
length = 1

for _ in range(N - 1) :
    a = int(eval(input()))
    a *= -1
    i = 0

    index = bisect.bisect_right(val, a)
    if index >= length :
        val.append(a)
        length += 1
    else :
        val[index] = a

print(length)

# Optimized solution
from bisect import bisect_right

N = int(eval(input()))
S = [1]

for _ in range(N):
    a = int(eval(input()))
    a *= -1
    i = bisect_right(S, a)

    if i == len(S):
        S.append(a)
    else:
        S[i] = a

print((len(S)))
# Original solution
from bisect import bisect_right

N = int(eval(input()))
S = [1]

for _ in range(N):
    a = int(eval(input()))
    a *= -1
    i = bisect_right(S, a)

    if i == len(S):
        S.append(a)
    else:
        S[i] = a

print((len(S)))

# Optimized solution
from bisect import bisect_right
import sys
input = sys.stdin.buffer.readline

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

dp = [10**10] * N

for a in A:
    a = -a
    dp[bisect_right(dp, a)] = a

ans = N - dp.count(10**10)
print(ans)