CodeEff/ECCO huggingface dataset:
# Original solution
import sys
input = sys.stdin.readline
import bisect
from collections import deque

def main():
    N = int(eval(input()))
    use = deque([10**9+1])
    for _ in range(N):
        num = int(eval(input()))
        if min(use) >= num:
            use.appendleft(num)
        else:
            index = bisect.bisect_left(use,num)
            use[index-1] = num
    
    print((len(use)-1))
    
if __name__ == "__main__":
    main()


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

def main():
    N = int(eval(input()))
    use = deque([int(eval(input()))])
    for _ in range(N-1):
        num = int(eval(input()))
        index = bisect.bisect_left(use,num)
        if index == 0:
            use.appendleft(num)
        else:
            use[index-1] = num
    
    print((len(use)))
    
if __name__ == "__main__":
    main()
# Original solution
import sys
input = sys.stdin.readline
import bisect
from collections import deque

def main():
    N = int(eval(input()))
    use = deque([int(eval(input()))])
    for _ in range(N-1):
        num = int(eval(input()))
        index = bisect.bisect_left(use,num)
        if index == 0:
            use.appendleft(num)
        else:
            use[index-1] = num
    
    print((len(use)))
    
if __name__ == "__main__":
    main()


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

def main():
    N = int(eval(input()))
    use = deque([10**9+1])
    for _ in range(N):
        num = int(eval(input()))
        index = bisect.bisect_left(use,num)
        if index == 0:
            use.appendleft(num)
        else:
            use[index-1] = num
    
    print((len(use)-1))
    
if __name__ == "__main__":
    main()
# Original solution
import sys, bisect
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = 10**20
def I(): return int(eval(input()))
def F(): return float(eval(input()))
def S(): return eval(input())
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()

def lis(a, colored):
    L = []
    L_idx = []
    ret = []
    for i, e in enumerate(a):
        if not colored[i]:
            idx = bisect.bisect_left(L, e)
            if idx==len(L):
                if len(L)>0:
                    ret.append(L_idx[-1])
                L.append(e)
                L_idx.append(i)
            else:
                idx = max(idx, 0)
                L[idx] = e
                L_idx[idx] = i
    ret.append(L_idx[-1])
    return ret

def resolve():
    N = I()
    A = [I()-1 for _ in range(N)]

    colored = [False]*N
    ans = 0
    while colored.count(False)>0:
        group = lis(A, colored)
        for i in group:
            colored[i] = True
        ans += 1

    print(ans)

if __name__ == '__main__':
    resolve()


# Optimized solution
import sys, bisect
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = 10**20
def I(): return int(eval(input()))
def F(): return float(eval(input()))
def S(): return eval(input())
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()

def lis_(a):
    dp = [INF]*len(a)
    for i in a:
        dp[bisect.bisect_left(dp, i+1)] = i
    return bisect.bisect_left(dp, INF)

def resolve():
    N = I()
    A = [I() for _ in range(N)]
    A = A[::-1]

    print((lis_(A)))

if __name__ == '__main__':
    resolve()
# Original solution
import bisect

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

colors = []
min_val = 10 ** 10
for num in nums:
	if num <= min_val:
		colors.insert(0, num)
		min_val = num
	else:
		idx_r = bisect.bisect_right(colors, num - 0.5) - 1
		colors[idx_r] = num
		min_val = max(colors[0], min_val)

print((len(colors)))


# Optimized solution
import bisect

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

colors = []
max_val = -1 * (10 ** 10)
for num in nums:
	if num >= max_val:
		colors.append(num)
		max_val = num
	else:
		idx_r = bisect.bisect_right(colors, num)
		colors[idx_r] = num
		max_val = min(colors[-1], max_val)

print((len(colors)))
# Original solution
import bisect

N = int(eval(input()))
Ali = [int(eval(input())) for _ in range(N)]
n = N
c = 0

while n > 0:
  dp = [Ali[0]]
  Ali2 = []
  for i in range(1,n):
    a = Ali[i]
    if a > dp[-1]:
      dp.append(a)
    else:
      b = bisect.bisect_left(dp, a)
      Ali2.append(dp[b])
      dp[b] = a
  Ali = Ali2[::1]
  n = len(Ali)
  c += 1
    
print(c)

# Optimized solution
from bisect import bisect
import heapq

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

for i in range(N):
  ii = bisect(q,A[i])
  if ii == len(q):
    heapq.heappush(q,A[i])
  else:
    q[ii] = A[i]
    
print((len(q)))
# Original solution
import sys
input = sys.stdin.readline
n = int(eval(input()))
a1 = int(eval(input()))
a = [a1]
for _ in range(n-1):
  ai = int(eval(input()))
  if ai <= a[-1]:
    a.append(ai)
  elif ai > a[0]:
    a = [ai]+a[1:]
  else:
    h = 0
    l = len(a)-1
    while l-h>1:
      m = (l+h)//2
      if ai > a[m]:
        l = m
      else:
        h = m
    a = a[:l]+[ai]+a[l+1:]
print((len(a)))   

# Optimized solution
def sub():
  import sys
  input = sys.stdin.readline
  n = int(eval(input()))
  a1 = int(eval(input()))
  a = [a1]
  ap = a.append
  for _ in range(n-1):
    ai = int(eval(input()))
    if ai <= a[-1]:
      ap(ai)
    elif ai > a[0]:
      a[0] = ai
    else:
      h = 0
      l = len(a)-1
      while l-h>1:
        m = (l+h)//2
        if ai > a[m]:
          l = m
        else:
          h = m
      a[l] = ai
  print((len(a)))   
sub()
# Original solution
from bisect import bisect_right

def main():    
    N = int(eval(input()))
    A = [int(eval(input())) for i in range(N)]
    n = [A.pop(-1)]
    A.reverse()
    
    for a in A:
        if n[-1] <= a: n.append(a)
        else: n[bisect_right(n, a)] = a
    
    print((len(n)))

if __name__ == '__main__':
    main()

# Optimized solution
import sys
from bisect import bisect_right

input = sys.stdin.readline

def main():
    N = int(eval(input()))
    A = [int(eval(input())) for _ in range(N)]
    n = [A.pop(-1)]
    A.reverse()
    
    for a in A:
        if n[-1] <= a: n.append(a)
        else: n[bisect_right(n, a)] = a
    
    print((len(n)))

if __name__ == '__main__':
    main()
# Original solution
import sys
import bisect
input=sys.stdin.readline

N=int(eval(input()))
A=[int(eval(input())) for _ in range(N)]
l=[]
n=-1
for x in A:
    if n<x:
        n=x
    elif len(l)>0:
        tmp=bisect.bisect_left(l,x)
        if tmp==0:l=[x]+l
        else:
            l[tmp-1]=x
    else:l.append(x)
print((len(l)+1))

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

N=int(eval(input()))
A=[-int(eval(input())) for _ in range(N)]
l=[A[0]]
for x in A[1::]:
    tmp=bisect.bisect(l,x)
    if tmp==len(l):l.append(x)
    else: l[tmp]=x
print((len(l)))
# Original solution

def binSearch(S, x):
    a = -1
    b = len(S)-1

    while(a + 1 < b):
        c = (a+b)//2
        if S[c] >= x:
            a = c
        else:
            b = c

    return b

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

    S = []

    for a in A:
        if len(S) == 0 or S[-1] >= a:
            S.append(a)
        else:
            p = binSearch(S, a)
            S[p] = a
    
    print((len(S)))


if __name__ == '__main__':
    main()


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

import bisect

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

Q = []
x = 0

for a in A:
    idx = bisect.bisect_right(Q, -a)

    if idx >= len(Q):
        x += 1
        Q.append(-a)
    else:
        Q[idx] = -a

print(x)
# Original solution
from heapq import heappop,heappush
n = int(eval(input()))
a = [-int(eval(input())) for i in range(n)]
x = [a[0]]
for i in range(1,n):
    if max(x)<=a[i]:
        heappush(x,a[i])
    else:
        p = heappop(x)
        y = [p]
        while p<=a[i]:
            p = heappop(x)
            y.append(p)
        heappush(x,a[i])
        for i in range(len(y)-1): heappush(x,y[i])
print((len(x)))

# Optimized solution
from bisect import bisect
n = int(eval(input()))
a = [-int(eval(input())) for i in range(n)]
x = [a[0]]
for i in range(1,n):
    if x[-1]<=a[i]: x.append(a[i])
    else: x[bisect(x,a[i])] = a[i]
print((len(x)))
# Original solution
#最長増加部分列問題 (LIS) 
import bisect

N = int(eval(input()))
seq = [0] * N
for i in range(N):
  seq[i] = int(eval(input()))

LIS = [seq[0]]
#print(LIS)
for i in range(1, len(seq)):
    if seq[i] <= LIS[0]:
        LIS.insert(0, seq[i])
    else:
        LIS[bisect.bisect_left(LIS, seq[i]) - 1] = seq[i]
    #print(LIS)
#print(LIS)
print((len(LIS)))

# Optimized solution
#最長増加部分列問題 (LIS) 
import bisect

N = int(eval(input()))
seq = [0] * N
for i in range(N):
  seq[i] = int(eval(input()))

LIS = [-1] * N
LIS[-1] = seq[0]
#print(LIS)
for i in range(1, len(seq)):
    LIS[bisect.bisect_left(LIS, seq[i]) - 1] = seq[i]
    #print(LIS)
#print(LIS)
c = LIS.count(-1)
print((len(LIS) - c))
# Original solution
import sys


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n = int(readline())
    a = [int(readline()) for _ in range(n)]
    cnt = 0
    while len(a):
        cnt += 1
        t_a = []
        mt = -1
        for i in range(len(a)):
            if mt >= a[i]:
                t_a.append(a[i])
            else:
                mt = a[i]
        a = t_a
    print(cnt)


if __name__ == '__main__':
    solve()


# Optimized solution
import sys
import bisect

def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n = int(readline())
    a = [int(readline()) for _ in range(n)]
    res = []
    for i in range(n-1, -1, -1):
        p = bisect.bisect_right(res, a[i])
        if len(res) == p:
            res.append(a[i])
        else:
            res[p] = a[i]
    print((len(res)))


if __name__ == '__main__':
    solve()
# Original solution
N = int(eval(input()))
A = [int(eval(input())) for i in range(N)]
arr = []
from bisect import bisect
for a in A:
    i = bisect(arr, -a)
    if i == len(arr):
        arr.append(-a)
    else:
        arr[i] = -a
print((len(arr)))

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

arr = []
for a in A:
    i = bisect(arr, -a)
    if i==len(arr):
        arr.append(-a)
    else:
        arr[i] = -a
print((len(arr)))
# Original solution
import bisect
from collections import deque

N = int(eval(input()))
a = []
for _ in range(N):
  a.append(int(eval(input())))

LIS = deque([a[0]])
for i in range(1,N):
    if a[i] > LIS[-1]:
    	LIS[-1] = a[i]
    elif LIS[0] >= a[i]:
    	LIS.appendleft(a[i])
    else:
    	LIS[bisect.bisect_left(LIS, a[i])-1] = a[i]

print((len(LIS)))


# Optimized solution
import bisect
from collections import deque

N = int(eval(input()))
a = []
for _ in range(N):
  a.append(int(eval(input())))

d = deque()
d.append(a[-1])
for i in reversed(list(range(N-1))):
	if a[i] >= d[-1]:
		d.append(a[i])
	else:
		index = bisect.bisect_right(d,a[i])
		d[index] = a[i]

print((len(d)))
# Original solution
#LIS
n=int(eval(input()))
lists=[0]*n
for i in range(n):
    lists[i]=int(eval(input()))
import bisect
counter=0
lislist=[lists[-1]]
for i in range(2,n+1):
    a=lists[-i]
    index=bisect.bisect_right(lislist,a)
    if index<len(lislist):
        lislist[index]=a

    elif index==len(lislist):
        lislist.append(a)

print((len(lislist)))


# Optimized solution
#!/usr/bin/env python
# -*- coding: utf-8 -*-
# sequence decomposing
import bisect
n = int(eval(input()))
lists = [int(eval(input())) for _ in range(n)]
lists = lists[::-1]
dataset = []
dataset.append(lists[0])
# datasetは単調増加なリストの値
for i in range(1, n):
    x = lists[i]
    if x >= dataset[-1]:
        dataset.append(x)
    elif x < dataset[-1]:
        index = bisect.bisect_right(dataset, x)
        dataset[index] = x
print((len(dataset)))
# Original solution
def resolve():
    import bisect
    n = int(eval(input()))
    a = [int(eval(input())) for _ in range(n)]
    m = []
    for i in range(n-1, -1, -1):
        if i == n-1:
            m.append(a[i])
        else:
            if m[-1] <= a[i]:
                m.append(a[i])
            elif m[0] > a[i]:
                m[0] = a[i]
            else:
                j = bisect.bisect_right(m, a[i])
                m[j] = a[i]
    print((len(m)))
resolve()

# Optimized solution
def resolve():
    import bisect
    n = int(eval(input()))
    a = [int(eval(input())) for _ in range(n)]
    m = []
    for i in range(n-1, -1, -1):
        if i == n-1:
            m.append(a[i])
        else:
            if m[-1] <= a[i]:
                m.append(a[i])
            else:
                j = bisect.bisect_right(m, a[i])
                m[j] = a[i]
    print((len(m)))

resolve()
# Original solution
import bisect

n = int(eval(input()))
# bisectが昇順のリストにしか対応していないのでマイナスをかける。
# -> ansの順序が昇順で管理できるようになる。最小値をans[-1]で管理する。
A = [- int(eval(input())) for _ in range(n)]

num = 1
ans = [A[0]]
for a in A[1:]:
  # ansの最小値以下の数値 -> append, else: a > ans[?] を満たす左端の?の値を書き換える。
  if a >= ans[-1]:
    ans.append(a)
    num += 1
  else:
    pos = bisect.bisect_right(ans, a) 
    ans[pos] = a 
print(num)

# Optimized solution
import bisect

n = int(eval(input()))
# bisectが昇順のリストにしか対応していないのでマイナスをかける。
# -> ansの順序が昇順で管理できるようになる。最小値をans[-1]で管理する。
A = [- int(eval(input())) for _ in range(n)]

ans = [A[0]]
for a in A[1:]:
  # ansの最小値以下の数値 -> append, else: a > ans[?] を満たす左端の?の値を書き換える。
  if a >= ans[-1]:
    ans.append(a)
  else:
    pos = bisect.bisect_right(ans, a) 
    ans[pos] = a 
print((len(ans)))
# Original solution
def getN():
    return int(eval(input()))
def getNM():
    return list(map(int, input().split()))
def getList():
    return list(map(int, input().split()))
from bisect import bisect_right

n = getN()
mx = []
k = 0
for i in range(n):
    num = -(getN())
    ins = bisect_right(mx, num)
    if ins == k:
        mx.append(num)
        k += 1
    else:
        mx[ins] = num
    # print(ins, mx)

print((len(mx)))

# Optimized solution
import sys
# from collections import defaultdict, deque
# import math
# import copy
from bisect import bisect_left, bisect_right
# import heapq

# sys.setrecursionlimit(1000000)

# input aliases
input = sys.stdin.readline

getS = lambda: input().strip()
getN = lambda: int(eval(input()))
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = 10 ** 20
MOD = 1000000007
def solve():
    n = getN()
    dp = [-INF]
    for i in range(n):
        num = getN()
        num = -num
        if num >= dp[-1]:
            dp.append(num)
        else:
            idx = bisect_right(dp, num)
            dp[idx] = num


    print((len(dp) - 1))
    return

def main():
    n = getN()
    for _ in range(n):
        solve()
if __name__ == "__main__":
    # main()
    solve()
# Original solution
import bisect
 
 
N = int(eval(input()))
 
lis = []
 
A1 = int(eval(input()))
 
 
lis.append(A1)
 
 
for i in range(N-1):
 
    A = int(eval(input()))
 
    flag = True
    ins = bisect.bisect_left(lis,A)
 
    if ins == 0:
        lis.insert(0,A)
 
    if lis[ins-1] < A:
        lis[ins-1] = A
 
"""
    for l in lis:
 
 
 
        if l < A:
            l = A
            flag = False
            lis.sort()
            maxi = max(maxi , i)
            break
 
    if flag:
        lis.append(A)
"""
 
#print (lis)
print((len(lis)))


# Optimized solution
import bisect

N = int(eval(input()))

A = []

for i in range(N):

    a = int(eval(input()))
    A.append(a)

A.reverse()

seq = [float("-inf")]

for i in A:

    ind = bisect.bisect_right(seq,i)

    if ind == len(seq):
        seq.append(i)
    else:
        seq[ind] = i

print((len(seq)-1))
# Original solution
import sys
import bisect
def input(): return sys.stdin.readline().rstrip()


def main():
    n = int(eval(input()))
    A=[0]*n
    for i in range(1,n+1):
        A[-i]=int(eval(input()))
    inf=10**10    
    dp=[inf]*(n+1)
    dp[0]=0
    for AA in A:
        bis=bisect.bisect_right(dp, AA)
        dp[bis]=AA #n以下の個数を数える
    print((bisect.bisect_right(dp, inf-100)-1))


if __name__ == '__main__':
    main()

# Optimized solution
import sys
import bisect
def input(): return sys.stdin.readline().rstrip()
 
 
def main():
    n = int(eval(input()))
    A=[0]*n
    for i in range(1,n+1):
        A[-i]=int(eval(input()))
    inf=10**10    
    dp=[0]
    for AA in A:
        if dp[-1]<=AA:
            dp.append(AA)
        else:
            bis=bisect.bisect_right(dp, AA)
            dp[bis]=AA #n以下の個数を数える
    print((len(dp)-1))
 
 
if __name__ == '__main__':
    main()
# Original solution
import bisect
N = int(eval(input()))
A = [int(eval(input())) for _ in range(N)]
b = []
for a in A[::-1]:
  idx = bisect.bisect_right(b, a)
  if len(b) <= idx:
    b.append(a)
  else:
    b[idx] = a

print((len(b)))


# Optimized solution
import bisect
import sys
input = sys.stdin.readline
N = int(eval(input()))
A = [int(eval(input())) for _ in range(N)]

dp = [float('inf')]*(N+1)
for a in A[::-1]:
  idx = bisect.bisect_right(dp, a)
  dp[idx] = a

ans = 0
for n in dp:
  if n != float('inf'):
    ans += 1
print(ans)
# Original solution
import heapq

N = int(eval(input()))
que = []
tmp = []
A1 = int(eval(input()))
heapq.heappush(que, A1*-1)
for _ in range(N-1):
    a = int(eval(input()))
    while True:
        if len(que) == 0:
            heapq.heappush(que, a*-1)
            break
        A = heapq.heappop(que)*-1
        if A < a:
            heapq.heappush(que, a*-1)
            break
        else:
            tmp.append(A)

    for val in tmp:
        heapq.heappush(que, val*-1)
    tmp = []

print((len(que)))

# Optimized solution
import bisect

N = int(eval(input()))
A = [-1]*N

for _ in range(N):
    val = int(eval(input()))
    n = bisect.bisect_left(A, val)
    A[n-1] = val

print((N-A.count(-1)))
# Original solution
# ABC134E

import sys
from bisect import bisect_left
input=sys.stdin.readline

def main():
    N=int(eval(input()))
    A=[int(eval(input())) for i in range(N)]
    
    lbds=[A[0]]
    for i in range(1,N):
        if lbds[-1]>=A[i]:
            lbds+=[A[i]]
        else:
            x=len(lbds)-bisect_left(lbds[::-1],A[i])
            lbds[x]=A[i]
            
    print((len(lbds)))
    
if __name__=="__main__":
    main()


# Optimized solution
# ABC134E

import sys
input=sys.stdin.readline

def bisectR(ite,x):
    st=-1
    en=len(ite)
    while(en-st>1):
        mid=(en+st)//2
        if ite[mid]<x:
            en=mid
        else:
            st=mid
    return en

def main():
    N=int(eval(input()))
    A=[int(eval(input())) for i in range(N)]
    
    lbds=[A[0]]
    for i in range(1,N):
        if lbds[-1]>=A[i]:
            lbds+=[A[i]]
        else:
            x=bisectR(lbds,A[i])
            lbds[x]=A[i]
    print((len(lbds)))
    
if __name__=="__main__":
    main()
# Original solution
import sys
from collections import deque, defaultdict
import copy
import bisect
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 9)

N = int(eval(input()))

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

B = []
for i in range(N):
	loc = bisect.bisect_left(B, A[i])
	if loc == 0:
		B = [A[i]] + B
	else:
		B[loc - 1] = A[i]

print((len(B)))

# Optimized solution

import sys
from collections import deque, defaultdict
import copy
import bisect
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 9)

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

B = []
min = -10000000000
for i in range(N):
	loc = bisect.bisect_right(B, -A[i])
	if loc == len(B):
		B.append(-A[i])
	else:
		B[loc] = -A[i]

print((len(B)))
# Original solution
from bisect import *

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

dp = [float("inf")]*N

for i in range(N) :
    ind = bisect_right(dp, A[i])
    dp[ind] = A[i]

ans = bisect_left(dp,float("inf"))
print(ans)


# Optimized solution
from bisect import *
N = int(eval(input()))
A = [-int(eval(input())) for i in range(N)]
dp = [float("inf")]*N
for a in A :
    ind = bisect_right(dp, a)
    dp[ind] = a
print((bisect_left(dp, float("inf"))))
# Original solution
#!/usr/bin/env python3
import sys
import bisect

def iterate_tokens():
    for line in sys.stdin:
        for word in line.split():
            yield word

def solve(N: int):
    tokens = iterate_tokens()
    colors_top = []
    for i in range(N):
        new = int(next(tokens))
        if colors_top:
            b = bisect.bisect_left(colors_top, new)
            if b == 0:
                colors_top = [new] + colors_top
            else:
                colors_top[b-1] = new
        else:
            colors_top.append(new)
    print((len(colors_top)))
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    solve(N)

if __name__ == '__main__':
    main()


# Optimized solution
#!/usr/bin/env python3
import sys
import bisect

def iterate_tokens():
    for line in sys.stdin:
        for word in line.split():
            yield word

def solve(N: int):
    tokens = iterate_tokens()
    colors_top = []
    for i in range(N):
        new = int(next(tokens))
        if colors_top:
            b = bisect.bisect_right(colors_top, -new)
            if b == len(colors_top):
                colors_top.append(-new)
            else:
                colors_top[b] = -new
        else:
            colors_top.append(-new)
    print((len(colors_top)))
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    solve(N)

if __name__ == '__main__':
    main()
# Original solution
import bisect
N = int(eval(input()))
A = [int(eval(input())) for _ in range(N)]
tmp = [A[0]]
for i in A[1:N]:
    index = bisect.bisect_left(tmp, i)
    if index == 0:
        tmp.insert(0, i)
    else:
        tmp[index-1] = i

print((len(tmp)))


# Optimized solution
import bisect
N = int(eval(input()))
A = [-int(eval(input())) for _ in range(N)]
tmp = [A[0]]
for i in A[1:N]:
    index = bisect.bisect(tmp, i)
    if index == len(tmp):
        tmp.append(i)
    else:
        tmp[index] = i

print((len(tmp)))
# 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:
    idx = bisect_left(dq, e)
    if idx == 0:
        dq.appendleft(e)
    else:
        dq[idx-1] = e

ans = len(dq)
print(ans)


# Optimized 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)
# Original solution
from bisect import bisect_left
n=int(eval(input()))
A=[int(eval(input())) for _ in range(n)]

DP=[[A[0]]]
for i in range(1,n):
    num,flag=A[i],1
    for j in range(len(DP)):
        if DP[j][-1]<num:
            DP[j].append(num)
            flag=0
            break
    if flag:DP.append([num])
    DP=sorted(DP, key=lambda x:x[-1], reverse=True)
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 DP[-1]<=num:
        DP.append(num)
    else:
        index=bisect_right(DP,num)
        DP[index]=num
print((len(DP)))