CodeEff/ECCO huggingface dataset:
# Original solution
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n = I()
    a = IR(n)
    a = [-i for i in a]
    dp = [float("inf")]*n
    for i in a:
        j = bisect.bisect_right(dp,i)
        dp[j] = i
    print((n-dp.count(float("inf"))))
    return

#Solve
if __name__ == "__main__":
    solve()


# Optimized solution
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.buffer.readline().split()]
def I(): return int(sys.stdin.buffer.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n = I()
    a = IR(n)
    dp = [float("inf")]*n
    for i in a:
        j = bisect.bisect_right(dp,-i)
        dp[j] = -i
    print((n-dp.count(float("inf"))))
    return

#Solve
if __name__ == "__main__":
    solve()
# Original solution
# -*- coding: utf-8 -*-

import sys
from collections import deque
from bisect import bisect_left

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(eval(input()))
def MAP(): return list(map(int, input().split()))
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

def LDS(A: list):
    L = deque([A[0]])
    for a in A[1:]:
        if a <= L[0]:
            # Lの先頭よりaが小さければ減少部分列を延長する(今回は広義(=を含む))
            L.appendleft(a)
        else:
            # そうでなければ、「a以上の最小要素の手前」をaにする
            # 該当位置は、二分探索で特定できる
            L[bisect_left(L, a)-1] = a
    return len(L)

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

print((LDS(A)))


# Optimized solution
# -*- coding: utf-8 -*-

import sys
from bisect import bisect_right

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(eval(input()))
def MAP(): return list(map(int, input().split()))
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

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

def LIS(A: list):
    L = [A[0]]
    for a in A[1:]:
        if a >= L[-1]:
            # aがLの末尾以上なら増加部分列を延長する(今回は広義(=を含む))
            L.append(a)
        else:
            # そうでなければ、「a以下の最大要素の次」をaにする
            # 該当位置は、二分探索で特定できる
            L[bisect_right(L, a)] = a
    return len(L)

# 後ろからLIS
print((LIS(A[::-1])))
# Original solution
from collections import deque
from bisect import bisect_left
n = int(eval(input()))
a = [int(eval(input())) for _ in range(n)]
ans = deque([a[0]])
for a_i in a[1:]:
    if ans[0] < a_i:
        i = bisect_left(ans, a_i)
        ans[i-1] = a_i
    else:
        ans.appendleft(a_i)

print((len(ans)))




# Optimized solution
from bisect import bisect_right
n = int(eval(input()))

color = [0] * (n+1)
for i in range(n):
    a = int(eval(input()))
    j = bisect_right(color, a)
    color[j-1] = a+1

ans = 0
for t in color:
    if t != 0:
        ans += 1

print(ans)
# Original solution
from bisect import bisect_right

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

L = [A[0]]
for a in A[1:]:
    if a >= L[-1]:
        L.append(a)
    else:
        L[bisect_right(L, a)] = a

print((len(L)))


# Optimized solution
from bisect import bisect
N = int(eval(input()))
A = [-int(eval(input())) for _ in range(N)]
L = [A[0]]
for a in A[1:]:
    if a >= L[-1]:
        L.append(a)
    else:
        L[bisect(L, a)] = a
print((len(L)))
# Original solution
import sys, collections

def count(q, ans):
    unused = collections.deque()
    ans += 1
    num = -1
    while q:
        n = q.popleft()
        if n <= num:
            unused.append(n)
        else:
            num = n
    return unused, ans

def solve():
    input = sys.stdin.readline
    N = int(eval(input()))
    col = 0
    q = collections.deque()
    for _ in range(N):
        q.append(int(eval(input())))

    while q:
        q, col = count(q, col)

    print(col)
    return 0

if __name__ == "__main__":
    solve()

# Optimized solution
import sys
from bisect import bisect_right, bisect_left

def solve():
    input = sys.stdin.readline
    N = int(eval(input()))
    A = [int(eval(input())) for _ in range(N)]
    col = [1] * N
    col[0] = -A[0]
    for a in A[1:]:
        index = bisect_right(col, -a)
        col[index] = -a
        #print(col, index)
    ans = bisect_right(col, 0)
    print(ans)

    return 0

if __name__ == "__main__":
    solve()
# Original solution
import bisect
import sys
input=sys.stdin.readline
from collections import deque
N=int(eval(input()))

cnt=0
L=[]
for i in range(N):
    n=int(eval(input()))
    L.append(n)
#print(L)
Q=[-1,10**10]
Q=deque()
#Q.appendleft(10**10)
#print(Q)
for i in range(N):
    if bisect.bisect_left(Q,L[i])==0:
        Q.appendleft(L[i])
    #elif bisect.bisect_left(Q,L[i])==len(Q)-1:
        #Q.insert(len(Q)-1,L[i])
    else:
        Q[bisect.bisect_left(Q,L[i])-1]=L[i]
#print(Q)
print((len(Q)))

# Optimized solution
N=int(eval(input()))
L=[1 for i in range(N+1)]
L[0]=-10**10

import bisect
for i in range(N):
    n=int(eval(input()))
    L[bisect.bisect_right(L,-n)]=-n
#print(L)
ans=0
for i in range(1,N+1):
    if L[i]==1:
        break
    ans+=1
print(ans)
# Original solution
import bisect
from collections import deque
n=int(eval(input()))
a=[int(eval(input())) for _ in range(n)]

q=[]
def bisect_desc(a,x):
    r = len(a)
    if r == 0:
        return 0
    l = 0
    while l != r:
        f = (l+r)//2
        if a[f] >= x:
            l = f+1
        else:
            r = f
    return l

for sa in a:
    t = bisect_desc(q,sa)
    if t ==len(q):
        q.append(sa)
    else:
        q[t] = sa

print((len(q)))

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

q=[]

def bisect_desc(a,x):
    r = len(a)
    if r == 0:
        return 0
    l = 0
    while l != r:
        f = (l+r)//2
        if a[f] >= x:
            l = f+1
        else:
            r = f
    return l

for sa in a:
    t = bisect_desc(q,sa)
    if t ==len(q):
        q.append(sa)
    else:
        q[t] = sa

print((len(q)))
# Original solution
N = int(eval(input()))
A = [int(eval(input())) for _ in range(N)]

from bisect import bisect_left, bisect_right, bisect, insort_left, insort_right, insort
from collections import deque
def solve(N,A):
    ans = 0
    lis = []
    for i in range(N):
        ind = bisect_left(lis,A[i])
        if ind == 0:
            lis.insert(0,A[i])
        else:
            lis[ind-1] = A[i]
    ans = len(lis)
    return ans
print((solve(N,A)))

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

from bisect import bisect_left, bisect_right, bisect, insort_left, insort_right, insort

def solve(N,A):
    ans = 0
    lis = []
    for i in range(N):
        ind = bisect_right(lis,-A[i])
        if ind == len(lis):
            lis.append(-A[i])
        else:
            lis[ind] = -A[i]
    ans = len(lis)
    return ans
print((solve(N,A)))
# Original solution
import bisect

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

colors = 0
a = A
while True:
    colors += 1
    p = [a[0]]
    pp = [0]
    for i in range(1,len(a)):
        if p[-1] < a[i]:
            p.append(a[i])
            pp.append(i)
        else:
            pos = bisect.bisect_left(p,a[i])
            p[pos] = a[i]
            pp[pos] = i

    if len(p) == len(a):
        break
    a = [a[x] for x in range(len(a)) if x not in pp]
print (colors)

# Optimized solution
import bisect

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

p = [A[0]]
for i in A[1:]:
    if p[-1] <= i:
        p.append(i)
    else:
        p[bisect.bisect_right(p,i)] = i
print((len(p)))
# Original solution
import bisect
import queue
INF=10**18
n=int(eval(input()))
a=queue.Queue()
for _ in range(n):
  a.put(int(eval(input())))
cnt=0
while a.qsize():
  dp=[]
  for i in range(a.qsize()):
    i=a.get()
    if bisect.bisect_left(dp,i)==len(dp):
      dp.append(i)
    else:
      a.put(bisect.bisect_left(dp,i))
      dp[bisect.bisect_left(dp,i)]=i
  cnt+=1
print(cnt)

# Optimized solution
import bisect
n=int(eval(input()))
a=[int(eval(input())) for _ in range(n)][::-1]
dp=[]
for i in a:
  if bisect.bisect_right(dp,i)==len(dp):
    dp.append(i)
  else:
    dp[bisect.bisect_right(dp,i)]=i
print((len(dp)))
# Original solution
from collections import defaultdict

N = int(eval(input()))
A = [int(eval(input())) for i in range(N)]
d = defaultdict(lambda: [])
for i,a in enumerate(A):
    d[a].append(i)
B = [None for i in range(N)]
for i,k in enumerate(sorted(d.keys())):
    for j in d[k]:
        B[j] = i

bit = [0] * (N+2)
def bit_add(a,w):
    x = a
    while x <= N+1:
        bit[x] += w
        x += (x & -x)

def bit_sum(a):
    x = a
    ret = 0
    while x > 0:
        ret += bit[x]
        x -= (x & -x)
    return ret

for a in B:
    a += 2

    s = bit_sum(a)
    bit_add(a,1)
    if s and bit_sum(a-1):
        t = bit_sum(a-1)
        ok = a-1
        ng = 0
        while ok-ng > 1:
            m = (ok+ng)//2
            if bit_sum(m) == t:
                ok = m
            else:
                ng = m
        bit_add(ok,-1)

    # for i in range(N+1):
    #     print(i+1, bit_sum(i+1))

print((bit_sum(N+1)))

# Optimized solution
from bisect import bisect
N = int(eval(input()))
A = [-int(eval(input())) for i in range(N)]

mem = []
for a in A:
    i = bisect(mem, a)
    if i==len(mem):
        mem.append(a)
    else:
        mem[i] = a
print((len(mem)))
# Original solution
import bisect

N=int(eval(input()))

line=[-1]*10**5

for _ in range(N):
    A=int(eval(input()))
    index=bisect.bisect_left(line,A)
    if index==0:
        line[0]=A
    else:
        line[index-1]=A
    line.sort()
    #print(line)
ans=[]
while line:
    num=line.pop(-1)
    if num==-1:
        break
    else:
        ans.append(num)

print((len(ans)))

# Optimized solution
import bisect
import collections

N=int(eval(input()))

line=collections.deque()

for _ in range(N):
    A=int(eval(input()))
    index=bisect.bisect_left(line,A)
    if index==0:
        line.appendleft(A)
    else:
        line[index-1]=A
    #print(line)
    
    #print(line)

print((len(line)))
# Original solution
from bisect import bisect_left
N = int(eval(input()))
A = [int(eval(input())) for i in range(N)]
X = [A[0]]

for i in range(1, N):
    if X[0] >= A[i]:
        X.insert(0, A[i])
    else:
        idx = bisect_left(X, A[i])
        X[idx-1] = A[i]

print((len(X)))


# Optimized solution
from bisect import bisect_right
N = int(eval(input()))
A = [int(eval(input())) for i in range(N)]
A.reverse()
X = [A[0]]

for i in range(1, N):
    if X[-1] <= A[i]:
        X.append(A[i])
    else:
        idx = bisect_right(X, A[i])
        X[idx] = A[i]

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

N = int(eval(input()))

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

q = deque([A[0]])

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

print((len(q)))

# Optimized solution
import bisect

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

def lis(S):
    from bisect import bisect_right
    L = [S[0]]

    for s in S[1:]:
        if s >= L[-1]:
            L.append(s)
        else:
            L[bisect_right(L, s)] = s
    return len(L)

print((lis(A[::-1])))
# Original solution
n=int(eval(input()))
tail=[int(eval(input()))]
import bisect
from collections import deque
tail=deque(tail)
c=1
for i in range(n-1):
    a=int(eval(input()))
    p=bisect.bisect_left(tail,a)
    if p==0:
        tail.appendleft(a)
        c+=1
    else:
        tail[p-1]=a
print(c)


# Optimized solution
import sys
input=sys.stdin.readline
n=int(eval(input()))
a_list=[int(eval(input())) for i in range(n)]
a_list.reverse()
INF=10**10
dp=[INF]*n
import bisect
for i in range(n):
    a=a_list[i]
    x=bisect.bisect_right(dp,a)
    dp[x]=a
ans=0
for i in range(n):
    if dp[i]!=INF:
        ans=i+1
print(ans)
# Original solution
from collections import deque
from bisect import bisect_left

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

dq = deque()
for e in a:
    i = bisect_left(dq, e)
    if i == 0:
        dq.appendleft(e)
    else:
        dq[i-1] = e

ans = len(dq)
print(ans)


# Optimized solution
from bisect import bisect_right

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

li = list()
for e in a:
    i = bisect_right(li, e)
    if i == len(li):
        li.append(e)
    else:
        li[i] = e

ans = len(li)
print(ans)
# Original solution
import sys
import bisect
from collections import deque
input = sys.stdin.readline
n = int(input().strip())
q = deque()
qappL = q.appendleft
for i in range(n):
  a = int(input().strip())
  b = bisect.bisect_left(q,a)
  if b == 0:
    qappL(a)
  else:
    q[b-1] = a
print((len(q)))

# Optimized solution
import sys
import bisect
input = sys.stdin.readline
n = int(input().strip())
q = [-int(input().strip())]
qapp = q.append
bis_r = bisect.bisect_right
for i in range(n-1):
  a = -int(input().strip())
  if q[-1] <= a:
    qapp(a)
  else:
    b = bis_r(q,a)
    q[b] = a
print((len(q)))
# Original solution
# -*- coding: utf-8 -*-
from collections import defaultdict
n = int(eval(input()))
a = [0 for _ in range(n)]
for i in range(n):
    a[i] = int(eval(input()))


colors = defaultdict(int)
colors[a[0]] += 1
for num in a[1:]:
    for cnum in sorted(set(colors.keys()), reverse=True):
        if num > cnum:
            if colors[cnum] == 1:
                colors.pop(cnum)
            else:
                colors[cnum] -= 1
            break
    colors[num] += 1
print((sum(colors.values())))

# Optimized solution
# -*- coding: utf-8 -*-
import bisect

n = int(eval(input()))
a = [0 for _ in range(n)]
for i in range(n):
    a[i] = -int(eval(input()))


LIS = list()
for i in a:
    j = bisect.bisect_right(LIS, i)
    if len(LIS) == j:
        LIS.append(i)
    else:
        LIS[j] = i

print((len(LIS)))
# Original solution
from bisect import bisect_right
n=int(eval(input()))
A=[int(eval(input())) for _ in range(n)][::-1]

DP=[A[0]]
for i in range(1,n):
    num=A[i]
    if num>=DP[-1]:
        DP.append(num)
    else:
        index=bisect_right(DP,num)
        DP[index]=num
print((len(DP)))

# Optimized solution
from _bisect import bisect_right
N=int(eval(input()))
A=[int(eval(input())) for _ in range(N)][::-1]

DP=[A[0]]
for i in range(1,N):
    num=A[i]
    if num>=DP[-1]:
        DP.append(num)
    else:
        index=bisect_right(DP,num)
        DP[index]=num
print((len(DP)))
# Original solution
from collections import deque
from bisect import bisect_left
N=int(eval(input()))
li=[]
ans=0
for i in range(N):
    a=-int(eval(input()))
    b=bisect_left(li,a+1)
    if b==len(li):
        li.append(a)
        ans+=1
    else:
        li[b]=a
print(ans)

# Optimized solution
from collections import deque
from bisect import bisect_left
N=int(eval(input()))
d=deque()
for i in range(N):
    A=int(eval(input()))
    b=bisect_left(d,A)-1
    if b==-1:
        d.appendleft(A)
    else:
        d[b]=A
print((len(d)))
# Original solution
from collections import Counter,defaultdict,deque
import sys
import copy
from itertools import permutations, combinations
from heapq import heappop, heappush
# input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
    
def inp(): # n=1
    return int(eval(input()))
def inpm(): # x=1,y=2
    return list(map(int,input().split()))
def inpl(): # a=[1,2,3,4,5,...,n]
    return list(map(int, input().split()))
def inpls(): # a=['1','2','3',...,'n']
    return list(input().split())
def inplm(n): # x=[] 複数行
    return list(int(eval(input())) for _ in range(n))
def inpll(n): # [[1,1,1,1],[2,2,2,2],[3,3,3,3]]
    return sorted([list(map(int, input().split())) for _ in range(n)])

def main():
    n=inp()
    a=inplm(n)
    aa=[-1 for _ in range(10**5)]
    index=0
    for i in range(n):
        for j in range(10**5):
            if a[i]>aa[j]:
                aa[j]=a[i]
                if index<j:
                    index=j
                break
    print((index+1))


if __name__ == "__main__":
    main()

# Optimized solution
import bisect
from collections import deque
def LIS(a):
    lis = deque()
    lis.append(-1)
    for i in range(len(a)):
        index = bisect.bisect_left(lis,a[i])
        if index == 0:
            lis.appendleft(a[i])
        else:
            lis[index-1] = a[i]
    return len(lis)

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

if __name__ == "__main__":
    main()
# Original solution
# ABC134-E

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return eval(input())

def main():
  n=I()
  l1=[I() for _ in range(n)]

  l1.reverse()
  l2=[0]*n

  # c=1

  # # print(l1)
  # for i,x in enumerate(l1):
  #   # print(l2)
  #   if l2[i]==0:
  #     l2[i]=i+1
  #   for j in range(i,n):
  #     y=l1[j]

  #     if c==n-1:
  #       return max(l2)

  #     if x>y and l2[j]==0:
  #       c+=1
  #       l2[j]=i+1
  #       x=y

  # return max(l2)

  l3=[]
  for x in l1:
    l3.append([x])
  # print(l3)
  i=0
  while True:
    if i>=len(l3):
      return len(l3)

    l4=[]
    a=l3[i]
    _a=l3[:i]
    # print(a)
    for j in range(i+1,len(l3)):
      b=l3[j]
      # print(a,b)
      if a[-1]>b[0]:
        a.append(b[0])
      else:
        l4.append(b)

    # print(a,l4)
    l4=_a+[a]+l4
    # print(l4)

    i+=1

    l3=copy.deepcopy(l4)


# main()
print((main()))


# Optimized solution
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
# def LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return eval(input())

def main():
  n=I()
  _l=[I() for _ in range(n)]
  l=collections.deque()

  for A in _l:
    if len(l)==0:
      l.append(A)
      continue

    lv=l[0]
    rv=l[-1]
    if rv<A:
      l[-1]=A
      continue
    if A<=lv:
      l.appendleft(A)
      continue

    li=0
    ri=len(l)-1
    while ri-li>1:
      mi=(ri+li)//2
      if l[mi]<A:
        li=mi
      else:
        ri=mi

    l[li]=A

  # print(l)
  return len(l)

# main()
print((main()))
# Original solution
from sys import stdin, setrecursionlimit
from bisect import bisect_left
from collections import deque

setrecursionlimit(10 ** 9)
INF = 1 << 60


def input():
    return stdin.readline().strip()


def main():
    N = int(eval(input()))
    A = tuple(int(eval(input())) for _ in range(N))
    B =deque([A[0]])

    for a in A[1:]:
        if a <= B[0]:
            B.appendleft(a)
        else:
            B[bisect_left(B, a) - 1] = a

    print((len(B)))


if __name__ == '__main__':
    main()


# Optimized solution
from sys import stdin, setrecursionlimit
from bisect import bisect_right

setrecursionlimit(10 ** 9)
INF = 1 << 60


def input():
    return stdin.readline().strip()


def main():
    N = int(eval(input()))
    A = tuple(int(eval(input())) for _ in range(N))
    B = [-A[0]]

    for a in A[1:]:
        if a <= -B[-1]:
            B.append(-a)
        else:
            B[bisect_right(B, -a)] = -a

    print((len(B)))


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


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

color = deque()

for a in A:
    pos = bisect_left(color, a)
    if pos == 0:
        color.appendleft(a)
    else:
        color[pos-1] = a

ans = len(color)
print(ans)

# Optimized solution
from bisect import bisect
inf = float('inf')

# 広義単調増加
def LIS(arr):
    N = len(arr)
    dp = [inf] * N
    res = 0
    for a in arr:
        pos = bisect(dp,a)
        dp[pos] = a
        res = max(res, pos + 1)
    return res

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

ans = LIS(A[::-1])
print(ans)
# Original solution
import bisect
from collections import deque
N=int(eval(input()))
a=[int(eval(input())) for _ in range(N)]
d=deque()

for i in range(N):
    p=bisect.bisect_left(d, a[i])
    #print(a[i], p, d)
    if p==0:
        d.appendleft(a[i])
    else:
        d[p-1]=a[i]
print((len(d)))

# Optimized solution
from collections import deque
import bisect
import sys

input = sys.stdin.readline
N = int(eval(input()))
A = [int(eval(input())) for _ in range(N)]
A = A[::-1]

col = [A.pop()]
col = deque(col)

while A:
    a = A.pop()
    if a <= col[0]:
        col.appendleft(a)
    else:
        x = bisect.bisect_left(col, a)
        col[x - 1] = a

ans = len(col)
print(ans)
# Original solution
import bisect
n = int(eval(input()))
A = [int(eval(input())) for i in range(n)]
m = 10**9
c = 0
X = []
for a in A:
    i = bisect.bisect_left(X, a)
    if i == 0:
        X.reverse()
        X.append(a)
        X.reverse()
    else:
        X[i-1] = a
print((len(X)))


# Optimized solution
import bisect
n = int(eval(input()))
A = [int(eval(input())) for i in range(n)]
m = 10**9
X = []
for a in A:
    i = bisect.bisect_right(X, -a)
    if i == len(X):
        X.append(-a)
    else:
        X[i] = -a
print((len(X)))