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):
from bisect import bisect_left
N = int(input())
memo = [-1]*N
for _ in range(N):
    a = int(input())
    idx = bisect_left(memo,a)-1
    memo[idx] = a

print(N-memo.count(-1))

Solution (Python):
from bisect import bisect
N = int(input())
dp = [1]*N
for _ in range(N):
  a=-int(input())
  n=bisect(dp,a)
  dp[n]=a
print(sum(1 for i in dp if i <= 0))

Solution (Python):
from bisect import bisect_left
from collections import deque
n = int(input())
a = [int(input()) for _ in range(n)]

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

Solution (Python):
import bisect, collections

n = int(input())
num = collections.deque([])
for i in range(n):
    a = int(input())
    temp = bisect.bisect_left(num, a)
    if temp == 0:
        num.appendleft(a)
    else:
        num[temp - 1] = a
print(len(num))

Solution (Python):
from bisect import bisect, bisect_left

N = int(input())
dp = [1]*N

for _ in range(N):
  a = -int(input())
  n = bisect(dp, a)
  dp[n] = a

print(sum( 1 for i in dp if i <= 0 ))

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

print(len(LIS))

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

print(len(LIS))

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

X = deque([])

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

Solution (Python):
from bisect import bisect_right


def main():
    n = int(input())
    a = [int(input()) for _ in range(n)]
    a.reverse()
    lis = [a[0]]
    for i in range(1, n):
        if a[i] >= lis[-1]:
            lis.append(a[i])
        else:
            lis[bisect_right(lis, a[i])] = a[i]
    print(len(lis))


if __name__ == '__main__':
    main()

Solution (Python):
n=int(input())
c=[]
hc=0
for i in range(n):
  a=int(input())
  l,r=-1,hc
  while r-l!=1:
    t=(l+r)//2
    if c[t]<a:
      r=t
    else:
      l=t
  if r==hc:
    c.append(a)
    hc+=1
  else:
    c[r]=a
print(hc)

Solution (Python):
from sys import *
from bisect import *

n = int(input())
a = list(map(int, stdin.readlines()))

dp = [1]
for j in a:
    j *= -1
    i = bisect(dp, j)
    if i < len(dp):
        dp[i] = j
    else:
        dp.append(j)
print(len(dp))

Solution (Python):
import bisect
N= int(input())
dp = [-1]*N
cnt =0
for i in range(N):
    a = int(input())
    idx = bisect.bisect_left(dp,a)
    dp[idx-1]=a
print(len(dp[bisect.bisect_left(dp,0):]))

Solution (Python):
import bisect
N= int(input())
dp = [-1]*N
cnt =0
for _ in range(N):
    a = int(input())
    idx = bisect.bisect_left(dp,a)
    dp[idx-1]=a
print(len(dp[bisect.bisect_left(dp,0):]))

Solution (Python):
import bisect
N= int(input())
dp = [-1]*N
cnt =0
for _ in range(N):
    a = int(input())
    idx = bisect.bisect_left(dp,a)
    dp[idx-1]=a
print(len(dp[bisect.bisect_left(dp,0):]))

Solution (Python):
from bisect import*
INF=10**18
n=int(input())
dp=[-1]*n
for _ in range(n):
  i=int(input())
  dp[bisect_left(dp,i)-1]=i
print(sum([i>=0 for i in dp]))

Solution (Python):
from collections import deque
import bisect
N=int(input())
L=deque()
for i in range(N):
  s=int(input())
  if i==0:
    L.append(s)
  else:
    if s<=L[0]:
      L.appendleft(s)
    else:
      L[bisect.bisect(L,s-1)-1]=s
print(len(L))

Solution (Python):
from bisect import bisect_right
def main():
    N = int(input())
    min_a = 10**9 + 1
    values = []
    ans = 0
    for i in range(N):
        tmp = -int(input())
        idx = bisect_right(values, tmp)
        if idx != len(values):
            values[idx] = tmp
        else:
            values.append(tmp)
            ans += 1

    print(ans)








main()

Solution (Python):
import sys
import math
from collections import defaultdict, deque, Counter
from copy import deepcopy
from bisect import bisect, bisect_right, bisect_left
from heapq import heapify, heappop, heappush
    
input = sys.stdin.readline
def RD(): return input().rstrip()
def F(): return float(input().rstrip())
def I(): return int(input().rstrip())
def MI(): return map(int, input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float,input().split()))
def Init(H, W, num): return [[num for i in range(W)] for j in range(H)]

def main():
    N = I()
    D = [float('inf')]*N
    for i in range(N):
        num = -I()
        index = bisect_right(D, num)
        D[index] = num

    res = 0
    for i in D:
        if i != float('inf'):
            res+=1
        else:
            break
    print(res)




if __name__ == "__main__":
    main()

Solution (Python):
N = int(input())
A = [int(input()) for _ in range(N)]
def solve(A,n):
    import bisect
    dp = [float('inf')] * n
    for i in range(n-1,-1,-1):
        k = bisect.bisect_right(dp, A[i])
        dp[k] = A[i]
    ans = 0
    for a in dp:
        if a != float('inf'):
            ans += 1
        else:
            break
    return ans
print(solve(A,N))

Solution (Python):
import bisect
from collections import deque

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

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

print(len(dq))

Solution (Python):
import sys
import bisect
def input(): return sys.stdin.readline().rstrip()
 
 
def main():
    n = int(input())
    A=[0]*n
    for i in range(1,n+1):
        A[-i]=int(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 
    print(len(dp)-1)
 
 
if __name__ == '__main__':
    main()

Solution (Python):
import bisect
import collections
import copy
import functools
import heapq
import math
import sys
from collections import deque
from collections import defaultdict
input = sys.stdin.readline
sys.setrecursionlimit(10**9)
MOD = 10**9+7


N = int(input())
seq = [int(input()) for _ in range(N)]
LIS = deque([seq[0]])
for i in range(1,len(seq)):
    if seq[i] <= LIS[0]:
        LIS.appendleft(seq[i])
    else:
        LIS[bisect.bisect_left(LIS, seq[i])-1] = seq[i]

print(len(LIS))

Solution (Python):
import bisect

N = int(input())
A = [int(input()) for _ in range(N)]
dp = [-1] * N
dp[N-1] = A[0]

ans = 0
for i in range(1, N):
    target_index = bisect.bisect_left(dp, A[i])
    dp[target_index-1] = A[i]

print(N - dp.count(-1))

Solution (Python):
'''
研究室PCでの解答
'''
import math

import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit


ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7 
dir = [(-1,0),(1,0),(0,-1),(0,1)]
alp = "abcdefghijklmnopqrstuvwxyz"

def main():
    n = int(ipt())
    ans = [-int(ipt())]
    for i in range(n-1):
        a = -int(ipt())
        if a >= ans[-1]:
            ans.append(a)
        else:
            ans[bisect.bisect_right(ans,a)] = a

    print(len(ans))

    return None

if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque
import sys, copy, itertools,bisect
input = sys.stdin.readline
  
n = int(input())
A = []
for i in range(n):
  a = int(input())
  A.append(a)
  
A.reverse() 

LDS =[A[0]] 

 
for i in range(1,n):
  x = A[i]
  index = bisect.bisect_right(LDS,x) 
  if index == len(LDS):
    LDS.append(x) 
  else:
    LDS[index]  = x
    



print(len(LDS))

Solution (Python):
from collections import deque
import sys, copy, itertools,bisect
input = sys.stdin.readline

def isOK(LIST, index, key):  
  if LIST[index] <= key:
    return True
  else:
    return False

def meguru_binary_search(LIST, key):
  ng = -1
  ok = len(LIST)
  while abs(ok-ng) > 1:
    mid = (ok + ng) //2 
    if isOK(LIST, mid, key):
      ok = mid
    else:
      ng = mid
  return ok  
  

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



LDS =[A[-1]] 

 
for i in range(2,n+1):
  x = A[-i]
  index = bisect.bisect_right(LDS,x)
  if index == len(LDS):
    LDS.append(x) 
  else:
    LDS[index]  = x
    


print(len(LDS))

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():

    
    from bisect import bisect_left, bisect_right, insort_right
    class SquareSkipList:
        
        

        def __init__(self, values=None, sorted_=False, square=1000, seed=42):
            
            
            
            
            

            self.cnt=0
            inf = float("inf")
            self.square = square
            if values is None:
                self.rand_y = seed
                self.layer1 = [inf]
                self.layer0 = [[]]
            else:
                self.layer1 = layer1 = []
                self.layer0 = layer0 = []
                if not sorted_:
                    values.sort()
                y = seed
                l0 = []
                for v in values:
                    y ^= (y & 0x7ffff) << 13
                    y ^= y >> 17
                    y ^= (y & 0x7ffffff) << 5
                    if y % square == 0:
                        layer0.append(l0)
                        l0 = []
                        layer1.append(v)
                    else:
                        l0.append(v)
                layer1.append(inf)
                layer0.append(l0)
                self.rand_y = y

        def add(self, x):  
            
            y = self.rand_y
            y ^= (y & 0x7ffff) << 13
            y ^= y >> 17
            y ^= (y & 0x7ffffff) << 5
            self.rand_y = y

            if y % self.square == 0:
                layer1, layer0 = self.layer1, self.layer0
                idx1 = bisect_right(layer1, x)
                layer1.insert(idx1, x)
                layer0_idx1 = layer0[idx1]
                idx0 = bisect_right(layer0_idx1, x)
                layer0.insert(idx1+1, layer0_idx1[idx0:])  
                del layer0_idx1[idx0:]
            else:
                idx1 = bisect_right(self.layer1, x)
                insort_right(self.layer0[idx1], x)

            self.cnt+=1

        def remove(self, x):  
            
            idx1 = bisect_left(self.layer1, x)
            layer0_idx1 = self.layer0[idx1]
            idx0 = bisect_left(layer0_idx1, x)
            if idx0 == len(layer0_idx1):
                del self.layer1[idx1]
                self.layer0[idx1] += self.layer0.pop(idx1+1)
            else:
                del layer0_idx1[idx0]

            self.cnt-=1

        def search_higher_equal(self, x):  
            idx1 = bisect_left(self.layer1, x)
            layer0_idx1 = self.layer0[idx1]
            idx0 = bisect_left(layer0_idx1, x)
            if idx0 == len(layer0_idx1):
                return self.layer1[idx1]
            return layer0_idx1[idx0]

        def search_higher(self, x):  
            idx1 = bisect_right(self.layer1, x)
            layer0_idx1 = self.layer0[idx1]
            idx0 = bisect_right(layer0_idx1, x)
            if idx0 == len(layer0_idx1):
                return self.layer1[idx1]
            return layer0_idx1[idx0]

        def search_lower(self, x):  
            
            idx1 = bisect_left(self.layer1, x)
            layer0_idx1 = self.layer0[idx1]
            idx0 = bisect_left(layer0_idx1, x)
            if idx0 == 0:  
                return self.layer1[idx1-1]
            return layer0_idx1[idx0-1]

        def pop(self, idx):
            
            
            
            self.cnt-=1
            layer0 = self.layer0
            s = -1
            for i, l0 in enumerate(layer0):
                s += len(l0) + 1
                if s >= idx:
                    break
            if s==idx:
                layer0[i] += layer0.pop(i+1)
                return self.layer1.pop(i)
            else:
                return layer0[i].pop(idx-s)


        def all(self):
            print(self.layer1)
            print(self.layer0)

        def len(self):
            return self.cnt

    

    N=I()


        
    ssl=SquareSkipList(square=2000)
    ssl.add(-1)
    
    
    for i in range(N):
        a=I()
        b=ssl.search_lower(a)
        if b==-1:
            pass
        else:
            ssl.remove(b)
        ssl.add(a)
        
        
    ans=ssl.len()-1
    print(ans)
            
        
    
        
    



main()

Solution (Python):
import bisect

N = int(input())
a = [int(input()) for _ in range(N)]
b = [a[-1]]
for i in range(2, N+1):
    x = a[-i]
    index = bisect.bisect_right(b, x)
    if index == len(b):
        b.append(x)
    else:
        b[index] = x
print(len(b))

Solution (Python):


import math

import itertools
from collections import deque
from collections import Counter
import heapq


import bisect
n=int(input())
d=[]
a=(int(input()))*-1
d.append(a)
ans=1
for i in range(n-1):
    a=-1*(int(input()))
    ind=bisect.bisect_right(d,a)
    l=len(d)
    if ind==l:
        d.append(a)
        ans+=1
    else:
        d[ind]=a
print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
from collections import deque

N = int(input())
A = [int(input()) for _ in range(N)]
INF = 10**18
arr = deque([])
for a in A:
    l, r = -1, len(arr)
    while (r-l) > 1:
        mid = (r+l)//2
        if arr[mid] < a:
            l = mid
        else:
            r = mid
    if l == -1:
        arr.appendleft(a)
    else:
        arr[l] = a
print(len(arr))

Solution (Python):
from bisect import bisect_right


N, *A = map(int, open(0).read().split())
A = [-a for a in A]
q = []
for a in A:
    idx = bisect_right(q, a)
    if idx == len(q):
        q.append(a)
    else:
        q[idx] = a
print(len(q))

Solution (Python):
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7






N = getN()
A = getArray(N)

def lis(A):
    L = deque([A[0]])
    for a in A[1:]:
        
        
        if a <= L[0]:
            L.appendleft(a)
        else:
            
            
            L[bisect_left(L, a) - 1] = a
    return len(L)

print(lis(A))

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




def RD(): return input().rstrip().decode()
def II(): return int(input())
def FI(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))


import bisect
from collections import deque

def main():
	n=II()
	A=[II() for _ in range(n)]

	Q=deque()
	Q.append(A[0])

	for i in A[1:]:
		x=bisect.bisect_left(Q,i)
		if x==0:
			Q.appendleft(i)
		else:
			Q[x-1]=i
	print(len(Q))





















if __name__ == "__main__":
	main()

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




def RD(): return input().rstrip().decode()
def II(): return int(input())
def FI(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))


import bisect
from collections import deque

def main():
	n=II()
	A=[II() for _ in range(n)]

	Q=deque()
	Q.append(A[0])

	for i in A[1:]:
		x=bisect.bisect_left(Q,i)
		if x==0:
			Q.appendleft(i)
		else:
			Q[x-1]=i
	print(len(Q))





















if __name__ == "__main__":
	main()

Solution (Python):
from collections import deque
from bisect import bisect_left
N=int(input())
d=deque()
for i in range(N):
    A=int(input())
    b=bisect_left(d,A)-1
    if b==-1:
        d.appendleft(A)
    else:
        d[b]=A
print(len(d))

Solution (Python):
from bisect import bisect_left
N = int(input())
A = [int(input()) for _ in range(N)]
L = [-1] * N
for a in A:
    idx = bisect_left(L, a)
    L[idx-1] = a
print(N - L.count(-1))

Solution (Python):
import bisect
n, *a = map(int, open(0).read().split())
a = a[::-1]
INF = 1 << 30
dp = [INF] * (n + 1)

for e in a:
    dp[bisect.bisect_right(dp, e)] = e
print(bisect.bisect_left(dp, INF))

Solution (Python):
n = int(input())
A = [int(input()) for _ in range(n)]

A.reverse()

import bisect
B = [10**18]
for a in A:
    i = bisect.bisect_right(B, a)
    if 0 <= i < len(B):
        B[i] = a
    else:
        B.append(a)
print(len(B))

Solution (Python):
import heapq
from bisect import bisect_left, bisect_right

n = int(input())
a = int(input())
q = [a*(-1)]


for _ in range(n-1):
    a = int(input())
    
    ind = bisect_right(q, a*(-1))
    ind = ind if 0 <= ind < len(q) else None
    if ind is None:
        q.append(a*(-1))
    else:
        q[ind] = a*(-1)

print(len(q))

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

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

D = deque([])

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

print(len(D))

Solution (Python):
import bisect

n = int(input())
seq = []
for i in range(n):
    seq.append(int(input()))
seq.reverse()
LIS = [seq[0]]
for i in range(1,len(seq)):
    if seq[i] >= LIS[-1]:
        LIS.append(seq[i])
    else:
        LIS[bisect.bisect_right(LIS, seq[i])] = seq[i]

print(len(LIS))

Solution (Python):
N = int(input())
A = []
for i in range(N):
    a = int(input())
    A.append(a)
B = [A[0]]
for i in range(1, N):

    if A[i] > B[-1]:
        sm = -1
        la = len(B)-1
        
        while sm+1<la:
            mi = (sm+la)//2
            if B[mi]<A[i]:
                la=mi
            else:
                sm=mi
        B[la]=A[i]
        
    else:
        B.append(A[i])

print(len(B))

Solution (Python):


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))

Solution (Python):
N = int(input())
A = list(int(input()) for _ in range(N))

S = [A[0]]
for i in range(1, N):
    if A[i] <= S[0]:
        S.insert(0, A[i])
        continue
    ok = 0
    ng = len(S)
    tmp = (ok+ng)
    while ok+1 < ng:
        tmp = (ok+ng)//2
        if A[i] > S[tmp]:
            ok = tmp
        else:
            ng = tmp
    S[ok] = A[i]
print(len(S))

Solution (Python):
N = int(input())
A = list(int(input()) for _ in range(N))

S = [A[0]]
for i in range(1, N):
    if A[i] <= S[0]:
        S.insert(0, A[i])
        continue
    ok = 0
    ng = len(S)
    tmp = (ok+ng)
    while ok+1 < ng:
        tmp = (ok+ng)//2
        if A[i] > S[tmp]:
            ok = tmp
        else:
            ng = tmp
    S[ok] = A[i]
print(len(S))

Solution (Python):

from collections import deque
from bisect import bisect_left

def main():
    N, *A = map(int, open(0))
    
    
    
    q = deque([])
    for i in range(N):
        d = bisect_left(q,A[i])
        if d == 0:
            q.appendleft(A[i])
        else:
            q[d-1] = A[i]
    print(len(q))

if __name__ == "__main__":
    main()

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

def binary_search(lis,i):
    ng = 0
    ok = len(lis)-1
    while abs(ok-ng) > 1:
        
        mid = (ok + ng) // 2
        if lis[mid] > i:
            ok = mid
        else:
            ng = mid
    return ok


d = [-1,1000000007]
for i in range(N):
    p = binary_search(d,A[i])
    if p == len(d)-1:
        d.append(A[i])
        d[-1],d[-2] = d[-2],d[-1]
    else:
        d[p] = A[i]
    
    
print(len(d)-2)

Solution (Python):
from bisect import bisect
import heapq

N = int(input())
A = [int(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))

Solution (Python):
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(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def TUPLE(): return tuple(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 

from decimal import *



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))

Solution (Python):
import sys
import bisect
def input(): return sys.stdin.readline().rstrip()


def main():
    n = int(input())
    A=[0]*n
    for i in range(1,n+1):
        A[-i]=int(input())
    inf=10**10    
    dp=[inf]*(n+1)
    dp[0]=0
    for AA in A:
        bis=bisect.bisect_right(dp, AA)
        dp[bis]=AA 
    print(bisect.bisect_right(dp, inf-100)-1)


if __name__ == '__main__':
    main()

Solution (Python):


import sys

N = int(input())
now = int(sys.stdin.readline().strip())
ans = [now]

for n in range(N - 1):
    now = int(sys.stdin.readline().strip())

    if now > ans[0]:
        ans[0] = now
    elif ans[-1] >= now:
        ans.append(now)
    else:
        
        left = 0  
        right = len(ans) - 1  

        while right - left > 1:
            mid = (right + left) // 2
            if now > ans[mid]:
                right = mid
            else:
                left = mid

        ans[right] = now

print(len(ans))

Solution (Python):


import sys
import bisect

N = int(input())
now = int(sys.stdin.readline().strip())
ans = [now]

for n in range(N - 1):
    now = int(sys.stdin.readline().strip())

    if now > ans[0]:
        ans[0] = now
    elif ans[-1] >= now:
        ans.append(now)
    else:
        
        left = 0  
        right = len(ans) - 1  

        while right - left > 1:
            mid = (right + left) // 2
            if now > ans[mid]:
                right = mid
            else:
                left = mid

        ans[right] = now

print(len(ans))

Solution (Python):
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(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def TUPLE(): return tuple(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 

from decimal import *



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)

Solution (Python):
from collections import deque
import bisect

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

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

print(len(Q))

Solution (Python):
from collections import deque
import bisect

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

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

print(len(Q))

Solution (Python):
from bisect import bisect_left

N = int(input())
A,c = list(range(N)),[]
for i in range(N):
	A[i] = int(input())

for x in reversed(A):
	p = bisect_left(c, x+1)
	if p == len(c):
		c.append(x)
	else:
		c[p] = x
print(len(c))

Solution (Python):
from bisect import bisect_left

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

for x in A:
	p = bisect_left(c, x+1)
	if p == len(c):
		c.append(x)
	else:
		c[p] = x
print(len(c))

Solution (Python):
import heapq
import bisect
N=int(input())
A=[]

for i in range(N):
  a=int(input())
  A.append(a)
h=[]
c=0
for i in range(N-1,-1,-1):
  p=bisect.bisect_right(h,A[i])
  if p==len(h):
    h.append(A[i])
    c+=1
  else:
    h[p]=A[i]
print(c)

Solution (Python):
from bisect import bisect_left, bisect_right
N = int(input())
seq = [0] * N
for i in range(N):
  seq[i] = (-1) * int(input())

"""

LIS = [seq[0]]
for i in range(len(seq)):
    if seq[i] >= LIS[-1]:
        LIS.append(seq[i])
    else:
        LIS[bisect_right(LIS, seq[i])] = seq[i]

print(len(LIS) - 1)

"""
def getLIS(_N,a):
  INF = 1e18
  MaxP = _N+10
  dp = [INF for _ in range(MaxP)]
  for i in range(_N):
    dp[bisect_right(dp,a[i])] = a[i]

  
  return dp[:bisect_left(dp, INF)]

LIS2 = getLIS(N,seq)

print(len(LIS2))

Solution (Python):
from bisect import bisect

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

ans = [1] * n
for ai in ma:
    tmp = bisect(ans, ai)
    ans[tmp] = ai
print(sum(num <= 0 for num in ans))

Solution (Python):
from bisect import bisect

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

ans = [ma[0]]
for ai in ma[1:]:
    tmp = bisect(ans, ai)
    if tmp == len(ans):
        ans.append(ai)
    elif tmp < len(ans):
        ans[tmp] = ai
print(len(ans))

Solution (Python):
import bisect, copy, heapq, math
from math import inf
import sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
def celi(a,b):
    return -(-a//b)
sys.setrecursionlimit(5000000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

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

now=n
lst=[-1]*n

for i in range(n):
    tmp=bisect.bisect_left(lst,a[i])
    if tmp==now:
        lst[tmp-1]=a[i]
        now-=1
    else:
        lst[tmp-1]=a[i]

print(n-now)

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

Solution (Python):


import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7
n=I()
lis=[I() for i in range(n)]
cols=deque([inf])
i=0
while i<n:
    
    x=lis[i]
    if cols[0]>=x:
        cols.appendleft(x)
    else:
        cols[bisect_left(cols,x)-1]=x
        
    i+=1

print(len(cols)-1)

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 bisect_right

N = int(input())
A = list(map(int, sys.stdin.readlines()))

print(LIS(A))

Solution (Python):
def LIS(A):
    dp = [-next(A)]
    for a in A:
        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 bisect_right

A = (int(input()) for _ in range(int(input())))

print(LIS(A))