Problem:
 Score : 500 points    Problem Statement You are given a sequence with N integers: A = \{ A_1, A_2, \cdots, A_N \} .
For each of these N integers, we will choose a color and paint the integer with that color. Here the following condition must be satisfied:   If A_i and A_j  (i < j) are painted with the same color, A_i < A_j .   Find the minimum number of colors required to satisfy the condition.      Constraints  1 \leq N \leq 10^5  0 \leq A_i \leq 10^9         Input Input is given from Standard Input in the following format:  N  A_1  :  A_N       Output Print the minimum number of colors required to satisfy the condition.        Sample Input 1 5
2
1
4
5
3      Sample Output 1 2  We can satisfy the condition with two colors by, for example, painting 2 and 3 red and painting 1 , 4 , and 5 blue.       Sample Input 2 4
0
0
0
0      Sample Output 2 4  We have to paint all the integers with distinct colors.

Solution (Python):
def LIS(A):
    dp = [-A[0]]
    for a in A[1:]:
        if -a >= dp[-1]:
            dp.append(-a)
        else:
            dp[bisect_right(dp, -a)] = -a
    return len(dp)



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

N = int(input())

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

print(LIS(A))

Solution (Python):
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(input())

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

print(LIS(A))

Solution (Python):
from _bisect import bisect_right
N=int(input())
A=[int(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))

Solution (Python):
from bisect import bisect_right
n=int(input())
A=[int(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))

Solution (Python):
import sys
readline = sys.stdin.readline

N = int(readline())
ans = []
import bisect
for i in range(N):
  a = -int(readline())
  ind = bisect.bisect_right(ans, a)
  if ind == len(ans):
    ans.append(a)
  else:
    ans[ind] = a
    
print(len(ans))

Solution (Python):
import bisect
n = int(input())
colors = [-int(input())]
for _ in range(n-1):
    a = int(input())
    i = bisect.bisect_right(colors, -a)
    if i == len(colors):
        colors.append(-a)
    else:
        colors[i] = -a
print(len(colors))

Solution (Python):

from bisect import bisect_right

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

INF = 10 ** 9 + 7
dp = [INF] * (N + 1)
for i in range(N):
    dp[bisect_right(dp, -X[i])] = -X[i]

print(sum(v < INF for v in dp))

Solution (Python):
import bisect
n = int(input())
colors = [-1]*(n+1)
for _ in range(n):
    a = int(input())
    idx = bisect.bisect_left(colors, a)-1
    colors[idx] = a
print(n-bisect.bisect_left(colors, 0)+1)

Solution (Python):
import bisect
n = int(input())
colors = [-1]*(n+1)
for _ in range(n):
    a = int(input())
    idx = bisect.bisect_left(colors, a)-1
    colors[idx] = a
print(colors[::-1].index(-1))

Solution (Python):
from bisect import bisect_left, bisect_right

def LIS(arr):  
    n = len(arr)
    lis = [arr[0]]
    for a in arr:
        if a > lis[-1]:
            lis.append(a)
        else:
            lis[bisect_left(lis, a)] = a
    return len(lis)

import sys
input = sys.stdin.readline

N = int(input())

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

print(LIS(A))

Solution (Python):
from bisect import bisect_right
def LIS(l):
    length = [l[0]]
    for i in range(1, len(l)):
        if l[i] >= length[-1]:
            length.append(l[i])
        else:
            pos = bisect_right(length, l[i])
            length[pos] = l[i]
    return len(length)

n = int(input())
a = [int(input()) for i in range(n)]
a = a[::-1]
print(LIS(a))

Solution (Python):
import sys
from bisect import bisect_right, bisect_left
read = sys.stdin.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7


def main():
    N = int(readline())
    A = list(int(readline()) for _ in range(N))

    LIS = [INF]*N
    A.reverse()
    for a in A:
        i = bisect_right(LIS,a)
        LIS[i] = a
    print(bisect_left(LIS, INF))


if __name__ == '__main__':
    main()

Solution (Python):

from bisect import bisect_left, bisect_right
n = int(input())
INF = 1010101010
dp = [INF] * n
a = [int(input()) for _ in range(n)]
a.reverse()
for i in a:
    dp[bisect_right(dp, i)] = i
print(bisect_left(dp, INF))

Solution (Python):
from bisect import bisect_left, bisect_right
n = int(input())
INF = 1010101010
dp = [INF] * n
a = [int(input()) for _ in range(n)]
a.reverse()
for i in a:
    dp[bisect_right(dp, i)] = i
print(bisect_left(dp, INF))

Solution (Python):



from bisect import bisect_left

N = int(input())
A = []
for _ in range(N):
    x = int(input())
    idx = bisect_left(A, x)
    if idx == 0:
        A.insert(idx, x)
    elif A[idx-1] == x:
        A.insert(idx, x)
    else:
        A[idx-1] = x

print(len(A))

Solution (Python):
import bisect
from collections import deque

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

buf = deque()
for a in A:
    i = bisect.bisect_right(buf, a-1)-1
    if i < 0:
        buf.appendleft(a)
    else:
        buf[i] = a
print(len(buf))

Solution (Python):
from bisect import bisect_right
N = int(input())
A = [int(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))

Solution (Python):
from bisect import bisect_left
N = int(input())
A = [int(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))

Solution (Python):
from bisect import bisect

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

def loopa():

    n=len(a)
    dp = [10**10]*(n+1)
    dp[0] = -10**10
    
    for i in range(n):
        idx = bisect(dp, a[i])
        dp[idx] = min(a[i], dp[idx])

    return dp

dp=loopa()        

print(bisect(dp, 10**10-1)-1)

Solution (Python):
from bisect import bisect

icase=1
if icase==1:
    n=int(input())
    a=[0]*n
    for i in range(n):
        a[i]=-int(input())
elif icase==2:
    n=5
    a=[-2,-1,-4,-5,-3]
elif icase==3:
    n=4
    a=[0,0,0,0]

def loopa():

    n=len(a)
    dp = [10**10]*(n+1)
    dp[0] = -10**10
    
    for i in range(n):

        idx = bisect(dp, a[i])
        dp[idx] = min(a[i], dp[idx])


    return dp

dp=loopa()        

print(bisect(dp, 10**10-1)-1)

Solution (Python):
from bisect import bisect_left
from collections import deque

N=int(input())
minList=deque([])
minmax=-1
for i in range(N):
  if i==0:
    a=int(input())
    minList.append(a)
    minmax=a
  else:
    a=int(input())
    if a<=minmax:
      minmax=a
      minList.appendleft(a)
    else:
      idx=bisect_left(minList,a)
      if idx==1:minmax=a
      minList[idx-1]=a
print(len(minList))

Solution (Python):
from bisect import bisect_left,bisect_right
n=int(input())
INF=float('inf')
l=[INF]*n
a=[int(input()) for _ in range(n)]
for i in a[::-1]:
    l[bisect_right(l,i)]=i
print(bisect_left(l,INF))

Solution (Python):
import sys
sys.setrecursionlimit(10**7) 
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right

from collections import deque, defaultdict


from collections import Counter

from itertools import accumulate,combinations,permutations,product

from heapq import heapify,heappop,heappush

from functools import reduce,lru_cache

from decimal import Decimal

def input(): 
    x=sys.stdin.readline()
    return x[:-1] if x[-1]=="\n" else x
def printe(*x):print("
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def binr(x): return bin(x)[2:]
def bitcount(x): 
    x= x - ((x >> 1) & 0x5555555555555555)
    x= (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x= (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f 
    x+= (x >> 8); x+= (x >> 16); x+= (x >> 32) 
    return x & 0x7f

def main():
    mod = 1000000007
    

    N = int(input())
    
    
    A = tuple(int(input()) for i in range(N)) 
    
    if N==1:
        print(1)
        return

    l=[-A[0]]
    for a in A[1:]:
        ind=bisect_right(l,-a)
        if ind==len(l):
            l.append(-a)
        else:
            l[ind]=-a
    print(len(l))






if __name__ == "__main__":
    main()

Solution (Python):
import sys
from collections import deque
from bisect import bisect_left

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n = int(input())
    A = list(int(input()) for _ in range(n))

    que = deque([A[0]])
    for i in range(1, n):
        idx = bisect_left(que, A[i])
        if idx == 0:
            que.appendleft(A[i])
        else:
            idx -= 1
            que[idx] = A[i]
    print(len(que))


if __name__ == '__main__':
    resolve()

Solution (Python):


import bisect







import sys

def input(): return sys.stdin.readline().rstrip()
def iIn(): return int(input())
def iInM(): return map(int, input().split())
def iInM1(): return map(int1, input().split())
def iInLH(): return list(map(int, input().split()))
def iInLH1(): return list(map(int1, input().split()))
def iInLV(n): return [iIn() for _ in range(n)]
def iInLV1(n): return [iIn()-1 for _ in range(n)]
def iInLD(n): return [iInLH() for _ in range(n)]
def iInLD1(n): return [iInLH1() for _ in range(n)]
def sInLH(): return list(input().split())
def sInLV(n): return [input().rstrip('\n') for _ in range(n)]
def sInLD(n): return [sInLH() for _ in range(n)]

def OutH(lst, deli=' '): print(deli.join(map(str, lst)))
def OutV(lst): print('\n'.join(map(str, lst)))

sys.setrecursionlimit(10 ** 6)

int1 = lambda x: int(x) - 1

INF = int(1e9)
MOD = 1000000007
dx = (-1, 0, 1, 0)
dy = (0, -1, 0, 1)


N = iIn()
A = iInLV(N)

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

print(len(lst))

Solution (Python):






import sys
input = sys.stdin.readline

import math

import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache





MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"






def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]


def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()


def DD(arg): return defaultdict(arg)


def inv(n): return pow(n, MOD-2, MOD)


kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret


def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr


def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors


def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum


def gcd(a, b):
    while b: a, b = b, a % b
    return a


def lcm(a, b):
    return a * b // gcd (a, b)


def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count


def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]


def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count





N = I()
A = ILs(N)

MAXS = [1 for i in range(N)]
for a in A:
  p = bisect.bisect_right(MAXS,-a)
  MAXS[p] = -a
ans = 0
for i in MAXS:
  if i != 1:
    ans += 1
  else:
    break
print(ans)

Solution (Python):
import bisect
n=int(input())
a=[int(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))

Solution (Python):
from bisect import bisect_right
N = int(input())
A = [int(input()) for _ in range(N)]
ans = 1
min_vs = [A[-1]]
for i in range(N-2, -1, -1):
    a = A[i]
    idx = bisect_right(min_vs, a)
    if idx == len(min_vs):
        ans += 1
        min_vs.append(a)
    else:
        min_vs[idx] = a
print(ans)

Solution (Python):
import bisect
from collections import deque
N = int(input())
A = deque([])
for i in range(N):
  A.append(int(input()))

dp = deque([])
l = len(A)
for i,a in enumerate(A):
  pos = bisect.bisect_left(dp, a)-1
  if pos<0:
    dp.appendleft(a)
  else:
    dp[pos] = a

print(len(dp))

Solution (Python):
import sys

def I(): return int(sys.stdin.readline().rstrip())

N = I()
A = [-I() for i in range(N)]



from bisect import bisect_left,bisect

def LNDS(l):  
    dp = [float('inf')]*(len(l)+1)
    dp[0] = -float('inf')
    for i in range(len(l)):
        j = bisect(dp,l[i])
        dp[j] = l[i]
    return bisect_left(dp,float('inf'))-1

print(LNDS(A))

Solution (Python):
import sys

def I(): return int(sys.stdin.readline().rstrip())

N = I()
A = [-I() for i in range(N)]



from bisect import bisect,bisect_left

def LIS(l):  
    dp = [float('inf')]*(len(l)+1)
    dp[0] = -float('inf')
    for i in range(len(l)):
        j = bisect(dp,l[i])
        dp[j] = l[i]
    return bisect_left(dp,float('inf'))-1

print(LIS(A))

Solution (Python):

import sys
input = sys.stdin.readline

def bisect_right_reverse(L, target):
    ok = len(L)
    ng = -1
    while ok - ng > 1:
        mid = (ok + ng) // 2
        if L[mid] < target:
            ok = mid
        else:
            ng = mid
    return ok

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

dp = [-1]  
for i in range(N):
    k = bisect_right_reverse(dp, A[i])
    if k == len(dp):
        dp.append(A[i])
    else:
        dp[k] = A[i]

print(len(dp))

Solution (Python):
import sys, math
from collections import defaultdict, deque, Counter
from bisect import bisect_left, bisect_right
from itertools import combinations, permutations, product
from heapq import heappush, heappop
from functools import lru_cache
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 1000000007
sys.setrecursionlimit(1000000)

N = ri()
A = []
for i in range(N):
	A.append(ri())

queue = deque()

queue.appendleft(A[0])
for i in range(1, N):
	idx = bisect_left(queue, A[i])
	if idx == 0:
		queue.appendleft(A[i])
	else:
		queue[idx-1] = A[i]
print(len(queue))

Solution (Python):
import sys, math
from collections import defaultdict
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 1000000007
sys.setrecursionlimit(1000000)

N = ri()
A = []
for i in range(N):
	A.append(ri())

import collections, bisect
queue = collections.deque()

queue.appendleft(A[0])
for i in range(1, N):
	idx = bisect.bisect_left(queue, A[i])
	if idx == 0:
		queue.appendleft(A[i])
	else:
		queue[idx-1] = A[i]
print(len(queue))

Solution (Python):

import sys
input = sys.stdin.readline

def bisect_right_reverse(L, target):
    ok = len(L)
    ng = -1
    while ok - ng > 1:
        mid = (ok + ng) // 2
        if L[mid] < target:
            ok = mid
        else:
            ng = mid
    return ok

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

L = []
for i in range(N):
    k = bisect_right_reverse(L, A[i])
    if k == len(L):
        L.append(A[i])
    else:
        L[k] = A[i]

print(len(L))

Solution (Python):
import sys
from collections import deque
from bisect import bisect_left

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n = int(input())
    A = list(int(input()) for _ in range(n))

    LIS = deque()
    for i in range(n):
        if len(LIS) == 0:
            LIS.appendleft(A[i])
        else:
            idx = bisect_left(LIS, A[i])
            if idx == 0:
                LIS.appendleft(A[i])
            else:
                LIS[idx - 1] = A[i]
    print(len(LIS))


if __name__ == '__main__':
    resolve()

Solution (Python):
from collections import deque
import bisect

N = int(input())
h = deque([int(input())])

for _ in range(N-1):
  a = int(input())
  i = bisect.bisect_left(h, a)
  if i == 0:
    h.appendleft(a)
  else:
    h[i-1] = a
    
print(len(h))

Solution (Python):
import sys
from bisect import bisect_right

input = sys.stdin.readline


def main():
    N = int(input())
    A = [0] * N
    for i in range(N):
        A[i] = int(input())

    A = [-a for a in A]

    colors = []
    for a in A:
        idx = bisect_right(colors, a)
        if idx == len(colors):
            colors.append(a)
        else:
            colors[idx] = a

    ans = len(colors)
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
import sys
from bisect import bisect_left

input = sys.stdin.readline


def main():
    N = int(input())
    A = [0] * N
    for i in range(N):
        A[i] = int(input())

    colors = []
    for a in A:
        idx = bisect_left(colors, a)
        if idx == 0:
            colors.insert(0, a)
        else:
            colors[idx - 1] = a

    ans = len(colors)
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
import sys
from bisect import bisect_left, insort_right

input = sys.stdin.readline


def main():
    N = int(input())
    A = [0] * N
    for i in range(N):
        A[i] = int(input())

    colors = []
    for a in A:
        idx = bisect_left(colors, a)
        if idx != 0:
            colors.pop(idx - 1)
        insort_right(colors, a)

    ans = len(colors)
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline 

from bisect import bisect



def solve(N, A):
    INF = 10**10

    dp = [INF]*(N+1)
    dp[0] = -1
    for a in A:
        idx = bisect(dp, a)
        dp[idx] = min(a, dp[idx])
    return max(i for i in range(N+1) if dp[i] < INF)

n = int(input())
a = [int(input()) for i in range(n)]
a.reverse()

print(solve(n, a))

Solution (Python):
from collections import deque
from bisect import bisect_left
N = int(input())
A = [int(input()) for _ in range(N)]
que = deque()
for i in range(N):
    k = bisect_left(que, A[i])
    if k == 0:
        que.appendleft(A[i])
    else:
        que[k - 1] = A[i]

print(len(que))

Solution (Python):
import sys
import itertools

import time
import math
import heapq
from collections import defaultdict
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines



MOD = 10 ** 4 + 7

N = int(input())

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

from collections import deque
d = deque([])
for a in A:
    l = -1
    r = len(d)
    while r - l > 1:
        m = l + (r - l) // 2
        if d[m] >= a:
            r = m
        else:
            l = m
    if r == 0:
        d.appendleft(a)
    else:
        d[r - 1] = a
print(len(d))

Solution (Python):
n=int(input())
a=[int(input()) for _ in range(n)]
ans=[-a[0]]
ansl=1
from bisect import bisect_right
for ai in a[1:]:
  tmp=bisect_right(ans,-ai)
  if tmp<ansl:
    ans[tmp]=-ai
  else:
    ans.append(-ai)
    ansl+=1
print(ansl)

Solution (Python):
def resolve():
    N = int(input())
    A = [int(input()) for _ in range(N)]
    import bisect
    import collections
    colormax = collections.deque([A[0]])
    for i in range(1, N):
        idx = bisect.bisect_left(colormax, A[i])
        if idx == 0:
            colormax.appendleft(A[i])
        else:
            colormax[idx-1] = A[i]
    print(len(colormax))



if '__main__' == __name__:
    resolve()

Solution (Python):
import bisect
N = int(input())
A = [int(input()) for i in range(N)]


S = []
for i in range(N):
    posi = bisect.bisect_left(S,A[i])
    if posi == 0:
        S.insert(0,A[i])
    else:
        S[posi-1] = A[i]

print(len(S))

Solution (Python):
from bisect import bisect_left
from collections import deque

n = int(input())
ans = []
ans.append(int(input()))
ans = deque(ans)
for i in range(n-1):  
  temp = int(input())
  if temp <= ans[0]:
    ans.appendleft(temp)
  else:
    ans[bisect_left(ans, temp)-1]=temp
print(len(ans))

Solution (Python):
from bisect import bisect_left
from collections import deque

n = int(input())
ans = []
ans.append(int(input()))
ans = deque(ans)
for i in range(n-1):  
  temp = int(input())
  if temp <= ans[0]:
    ans.appendleft(temp)
  else:
    ans[bisect_left(ans, temp)-1]=temp
print(len(ans))

Solution (Python):
from bisect import bisect_left
from collections import deque

n = int(input())
ans = []
ans.append(int(input()))
ans = deque(ans)
for i in range(n-1):  
  temp = int(input())
  
  if temp <= ans[0]:
    
    
    
    ans.appendleft(temp)
  else:
    ans[bisect_left(ans, temp)-1]=temp

print(len(ans))

Solution (Python):
N=int(input())
L=[1 for i in range(N+1)]
L[0]=-10**10

import bisect
for i in range(N):
    n=int(input())
    L[bisect.bisect_right(L,-n)]=-n

ans=0
for i in range(1,N+1):
    if L[i]==1:
        break
    ans+=1
print(ans)

Solution (Python):
def bisect_left_reverse(a, x):
    if a[0] <= x:
        return 0
    if x < a[-1]:
        return len(a)
    ok = len(a) - 1
    ng = 0
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if a[mid] <= x:
            ok = mid
        else:
            ng = mid
    return ok
def bisect_right_reverse(a, x):
    if a[0] < x:
        return 0
    if x <= a[-1]:
        return len(a)
    ok = len(a) - 1
    ng = 0
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if a[mid] < x:
            ok = mid
        else:
            ng = mid
    return ok
  
n = int(input())
data = [int(input())]

for i in range(n-1):
  a = int(input())
  idx = bisect_right_reverse(data, a)
  if idx == len(data):
    data.append(a)
  else:
    data[idx] = a

print(len(data))

Solution (Python):
from bisect import bisect_left, bisect_right
import sys
input = sys.stdin.readline

n = int(input())
col_maxs = []
for _ in range(n):
    a = int(input()) * (-1)
    if not col_maxs:
        col_maxs.append(a)
        continue

    curr_max = col_maxs[-1]
    if a >= curr_max:
        col_maxs.append(a)
    else:
        
        ind = bisect_right(col_maxs, a)
        col_maxs[ind] = a

print(len(col_maxs))

Solution (Python):
from bisect import bisect_left, bisect_right

n = int(input())
col_maxs = []
for _ in range(n):
    a = int(input()) * (-1)
    if not col_maxs:
        col_maxs.append(a)
        continue

    curr_max = col_maxs[-1]
    if a >= curr_max:
        col_maxs.append(a)
    else:
        
        ind = bisect_right(col_maxs, a)
        col_maxs[ind] = a

print(len(col_maxs))

Solution (Python):
import bisect
from collections import deque
N = int(input())
nums = deque([])

for i in range(N):
    num = int(input())
    if i == 0:
        nums.append(num)
    else:
        if nums[-1] < num:
            nums[-1] = num
        else:
            insert_index = bisect.bisect_left(nums, num)
            if insert_index == 0:
                nums.appendleft(num)
            else:
                nums[insert_index - 1] = num


print(len(nums))

Solution (Python):
from bisect import bisect_right, insort_right
N = int(input())
A = [int(input()) for _ in range(N)][::-1]
res = [A[0]]
for a in A[1:]:
    idx = bisect_right(res, a)
    if idx == len(res):
        res.append(a)
    else:
        if res[idx] == a:
            insort_right(res, a)   
        else:
            res[idx] = a
print(len(res))

Solution (Python):
from bisect import bisect_right

N, *A = 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))

Solution (Python):
from collections import deque
from bisect import bisect_left

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

dp = deque([])
b = []
for i in range(n):
    j = bisect_left(dp, a[i])
    if j == 0:
        dp.appendleft(a[i])
    else:
        dp[j-1] = a[i]

print(len(dp))

Solution (Python):
N = int(input())
A = [int(input()) for i in range(N)]

import bisect

bilist = [A[0]]
ans = 0

for a in A[1:]:
    index = bisect.bisect_left(bilist,a)
    if index == 0:
        bisect.insort_left(bilist,a)
    else:
        bilist[index-1] = a


print(len(bilist))

Solution (Python):
from bisect import bisect_left,bisect
 
n = int(input())
p = [-1*int(input())]
for i in range(n-1):
    now = -1*int(input())
    if now >= p[-1]:
        p.append(now)
    else:
        p[bisect(p,now)] = now
print(len(p))

Solution (Python):
import bisect


def main():
    INF = 10 ** 10
    N = int(input())
    A = [int(input()) for _ in range(N)]
    A.reverse()
    B = [INF for _ in range(N)]
    for a in A:
        index = bisect.bisect_right(B, a)
        B[index] = a
    ans = 0
    for b in B:
        if b == INF:
            break
        ans += 1
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
n = int(input())
a = []
for i in range(n):
    ai = int(input())
    a.append(ai)

lst = [a[0]]
for i in range(1, n):
    ai = a[i]
    left = -1
    right = len(lst)
    while left+1 < right:
        mid = (left + right) // 2
        if lst[mid] < ai:
            right = mid
        else:
            left = mid
    if right == len(lst):
        lst.append(ai)
    else:
        lst[right] = ai
print(len(lst))

Solution (Python):
from bisect import bisect
N, *A = map(int, open(0).read().split())

mins = []
length = 0
for a in A:
    i = bisect(mins, -a)
    if i >= length:
        mins.append(-a)
        length += 1
    else:
        mins[i] = -a
print(length)

Solution (Python):
from bisect import *
def solve():
    ans = 0
    N = int(input())
    A = [-int(input()) for _ in range(N)]
    lis = [A[0]]
    for i in range(1,N):
        if A[i]>=lis[-1]:
            lis.append(A[i])
        else:
            ind = bisect_right(lis,A[i])
            lis[ind] = A[i]
    ans = len(lis)
    return ans
print(solve())

Solution (Python):
def binary_search(key):
    bad, good = -1, len(ans)
    while good - bad > 1:
        mid = (bad + good) // 2
        if ans[mid][-1] < key:
            good = mid
        else:
            bad = mid
    return good


N = int(input())
ans = []
for _ in range(N):
    A = int(input())
    idx = binary_search(A)
    if idx == len(ans):
        ans.append([A])
    else:
        ans[idx].append(A)
print(len(ans))

Solution (Python):
n=int(input())
m=[]
m.append(int(input()))
count=1
for i in range(n-1):
  k=int(input())
  if k<=m[-1]:
    m.append(k)
    count+=1
  else:
    r=count-1
    l=0
    while l+1<r:
      try1=(r+l)//2
      if m[try1]>=k:
        l=try1
      else:
        r=try1
    if m[l]>=k:
      m[r]=k
    else:
      m[l]=k
print(count)

Solution (Python):
n=int(input())
a=[int(input())for _ in range(n)]
dp=[2]*(n+1)
from bisect import bisect_left,bisect_right
for i in a:
  dp[bisect_left(dp,-i+1)]=-i
print(dp.index(2))

Solution (Python):
import bisect
n = int(input())
a = [int(input()) for i in range(n)][::-1]

color_num = [a[0]]
for i in range(1, n):
    if a[i] >= color_num[-1]:
        color_num.append(a[i])
    else:
        temp = bisect.bisect_right(color_num, a[i])
        color_num[temp] = a[i]


print(len(color_num))

Solution (Python):






import unittest
from io import StringIO
import sys
sys.setrecursionlimit(10 ** 5 + 10)


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


def resolve():
    n = int(input())
    seq = [int(input()) for _ in range(n)][::-1]

    """
    Longest Increasing/Decreasing Subsuquence (LIS, LDS)
    Verified:
        https://atcoder.jp/contests/abc134/tasks/abc134_e
        https://onlinejudge.u-aizu.ac.jp/courses/library/7/DPL/all/DPL_1_D
    """


    def longest_subsequence(A: "Array[int]", equals: bool, increasing: bool) -> int:
        """
        Compute the length of LIS or LDS.
        
        Args:
            A ("Array[int]"): a list or tuple to compute.
            equals (bool): permit adjacent numbers in subsequence to equal.
            increasing (bool): compute an increasing subsequence or decreasing one.
        Returns: (int) the length of a subsequence.
        """
        from bisect import bisect_left, bisect_right

        bs = bisect_right if equals else bisect_left
        compare = (lambda x, y: x >= y) if equals else (lambda x, y: x > y)
        if not increasing:
            A = A[::-1]

        dp = [A[0]]  
        for i in A[1:]:
            if compare(i, dp[-1]):
                dp.append(i)
            else:
                dp[bs(dp, i)] = i
        return len(dp)
    
    print(longest_subsequence(seq,True,True))

    
    




resolve()