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 bisect_right_rev(lst, x):
    if lst[0] < x:
        return 0
    if x <= lst[-1]:
        return len(lst)

    a = 0
    b = len(lst) - 1

    while abs(b - a) > 1:
        c = (a + b) // 2

        if lst[c] < x:
            b = c
        else:
            a = c
    
    return b

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

for i in range(N):
    if len(seq) == 0:
        seq.append(A[i])
    else:
        ind = bisect_right_rev(seq, A[i])
        if ind == len(seq):
            seq.append(A[i])
        else:
            seq[ind] = A[i]

print(len(seq))

Solution (Python):
import bisect
def get_LIS(seq):
    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))


N = int(input())
A = [int(input()) for _ in range(N)]
A = A[::-1]
get_LIS(A)

Solution (Python):
import bisect

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

A.reverse()

dp = [A[0]]

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

print(len(dp))

Solution (Python):
import sys
from bisect import bisect_left

def bisect_left_reverse(a, x):
    '''
    reverseにソートされたlist aに対してxを挿入できるidxを返す。
    xが存在する場合には一番左側のidxとなる。
    '''
    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):
    '''
    reverseにソートされたlist aに対してxを挿入できるidxを返す。
    xが存在する場合には一番右側のidx+1となる。
    '''
    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

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

multi_lis = []
for a_i in A:
    if not multi_lis:
        multi_lis.append(a_i)
        continue

    if a_i <= multi_lis[-1]:
        multi_lis.append(a_i)
    else:
        p = bisect_right_reverse(multi_lis, a_i)
        multi_lis[p] = a_i 

print(len(multi_lis))

Solution (Python):


import sys 
from bisect import bisect_right

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N = int(readline())
A = list(map(int,read().split()))
X = [-1]*N
for a in A:
    i = bisect_right(X,a-1)-1
    X[i] = a
print(N - X.count(-1))

Solution (Python):


import sys 
from bisect import bisect_left
from collections import deque

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N = int(readline())
A = list(map(int,read().split()))


INF = 10**31
q = deque([])

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

Solution (Python):
from bisect import bisect_right

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

lst = [a[0]]
for aa in a[1:]:
    i = bisect_right(lst, aa)
    if i == len(lst): lst.append(aa)
    else: lst[i] = aa

print(len(lst))

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)
  if b==0:
    d.appendleft(a)
  else:
    d[b-1]=a 
print(len(d))

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

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

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

Solution (Python):
from collections import deque
import bisect

N = int(input())
table = deque()
for n in range(N):
    a = int(input())
    if n == 0:
        table.append(a)
    else:
        if a <= table[0]:
            table.appendleft(a)
        else:
            table[bisect.bisect_left(table, a)-1] = a
            
print(len(table))

Solution (Python):
from collections import deque
import bisect

N = int(input())
table = deque()
for n in range(N):
    a = int(input())
    if n == 0:
        table.append(a)
    else:
        if a <= table[0]:
            table.appendleft(a)
        else:
            table[bisect.bisect_left(table, a)-1] = a
            
print(len(table))

Solution (Python):
from bisect import bisect_left as bl
N=int(input())
A=[int(input()) for _ in [0]*N]
def bl3(A,x):
    
    
    ok=len(A)
    ng=-1
    while abs(ok-ng)>1:
        mid=(ok+ng)//2
        if A[mid]<x:
            ok=mid
        else:
            ng=mid
    return ok

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

Solution (Python):
code = """






from libcpp.utility cimport pair
from libcpp.string cimport string
from libcpp.vector cimport vector
from cython.operator cimport dereference
from libcpp cimport bool
from cython.operator cimport preincrement
from libc.stdio cimport getchar, printf
from cython.operator cimport predecrement
cpdef inline vector[int] ReadInt(int n):
    cdef int b, c
    cdef vector[int] *v = new vector[int]()
    for i in range(n):
        c = 0
        while 1:
            b = getchar() - 48
            if b < 0: break
            c = c * 10 + b
        v.push_back(c)
    return v[0]

cpdef inline vector[string] Read(int n):
    cdef char c
    cdef vector[string] *vs = new vector[string]()
    cdef string *s
    for i in range(n):
        s = new string()
        while 1:
            c = getchar()
            if c<=32: break
            s.push_back(c)
        vs.push_back(s[0])
    return vs[0]

cpdef inline void PrintLongN(vector[long] l):
    cdef int n = l.size()
    for i in range(n): printf("%ld\\n", l[i])

cpdef inline void PrintLong(vector[long] l):
    cdef int n = l.size()
    for i in range(n): printf("%ld ", l[i])
cdef extern from "<set>" namespace "std" nogil:
    cdef cppclass multiset[T]:
        ctypedef T value_type
        cppclass iterator:
            T& operator*()
            iterator operator++()
            iterator operator--()
            bint operator==(iterator)
            bint operator!=(iterator)
        cppclass reverse_iterator:
            T& operator*()
            iterator operator++()
            iterator operator--()
            bint operator==(reverse_iterator)
            bint operator!=(reverse_iterator)
        cppclass const_iterator(iterator):
            pass
        cppclass const_reverse_iterator(reverse_iterator):
            pass
        multiset() except +
        multiset(multiset&) except +
        iterator begin()
        reverse_iterator rbegin()
        size_t count(const T&)
        bint empty()
        iterator end()
        reverse_iterator rend()
        iterator find(T&)
        size_t size()
        iterator upper_bound(const T&)
        iterator lower_bound(T&)
        pair[iterator, bint] insert(const T&) except +
        iterator erase(iterator)

cdef extern from *:
    ctypedef long long ll "long long"


cdef class MultiSet:
    cdef multiset[ll] *_thisptr
    def __cinit__(self):
        self._thisptr = new multiset[ll]()
    cpdef int size(self):
        return self._thisptr.size()
    cpdef bool empty(self):
        return self._thisptr.empty()
    cpdef void add(self, ll x):
        self._thisptr.insert(x)
    cpdef void remove(self, ll x):
        self._thisptr.erase(self._thisptr.find(x))
    cpdef int count(self, ll x):
        return self._thisptr.count(x)
    cpdef ll min(self):
        return dereference(self._thisptr.begin())
    cpdef ll max(self):
        return dereference(self._thisptr.rbegin())
    def lower_bound(self, x):
        cdef multiset[ll].iterator itr = self._thisptr.lower_bound(x)
        if itr == self._thisptr.end():
            return None
        else:
            return dereference(itr)
    def upper_bound(self, ll x):
        cdef multiset[ll].iterator itr = self._thisptr.upper_bound(x)
        if itr == self._thisptr.end():
            return None
        else:
            return dereference(itr)
    def next(self, x):
        if x >= self.max():
            return None
        cdef multiset[ll].iterator itr = self._thisptr.find(x)
        cdef int c = self._thisptr.count(x)
        for i in range(c):
            preincrement(itr)
        return dereference(itr)
    cpdef prev(self, x):
        if x <= self.min():
            return None
        cdef multiset[ll].iterator itr = self._thisptr.find(x)
        predecrement(itr)
        return dereference(itr)
    cpdef ll pop_min(self):
        cdef multiset[ll].iterator itr = self._thisptr.begin()
        cdef ll ret = dereference(itr)
        self._thisptr.erase(itr)
        return ret
    cpdef ll pop_max(self):
        cdef multiset[ll].reverse_iterator itr = self._thisptr.rbegin()
        cdef ll ret = dereference(itr)
        self._thisptr.erase(self._thisptr.find(ret))
        return ret
    def __contains__(self, x):
        if self._thisptr.find(x)==self._thisptr.end():
            return False
        else:
            return True
"""


import os, sys, getpass

if sys.argv[-1] == 'ONLINE_JUDGE':
    code = code.replace("USERNAME", getpass.getuser())
    open('atcoder.pyx','w').write(code)
    os.system('cythonize -i -3 -b atcoder.pyx')
    sys.exit(0)


from atcoder import MultiSet, ReadInt

def main():
    ms = MultiSet()
    N = ReadInt(1)[0]
    for i in range(N):
        A = ReadInt(1)[0]
        if ms.empty():
            ms.add(A)
            continue
        if A <= ms.min():
            ms.add(A)
        else:
            b = ms.lower_bound(A)
            if b is None:
                ms.pop_max()
                ms.add(A)
            else:
                c = ms.prev(b)
                ms.remove(c)
                ms.add(A)
    print(ms.size())

if __name__ == "__main__":
    main()

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


def main():
    input = sys.stdin.buffer.readline
    n = int(input())
    a = [int(input()) for _ in range(n)]
    pile = deque()
    for i in range(n):
        index = bisect_left(pile, a[i])
        if index == 0:
            pile.appendleft(a[i])
        else:
            pile[index - 1] = a[i]
    print(len(pile))


if __name__ == "__main__":
    main()

Solution (Python):
from bisect import bisect_right

def main():
    inf=float("inf")
    n=int(input())
    alst=[int(input()) for _ in range(n)]
    work=[inf]*n
    for i in range(n-1,-1,-1):
        j=bisect_right(work,alst[i])
        work[j]=alst[i]
    print(n-work.count(inf))

main()

Solution (Python):
import sys
import bisect

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


c = []
for a in A:
    a *= -1
    i = bisect.bisect_right(c, a)
    if i == len(c):
        c.append(a)
    else:
        c[i] = a
print(len(c))

Solution (Python):
import bisect
from collections import deque

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

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

for i in range(1, N):
    ind = bisect.bisect_left(dp, A[i])

    if ind == 0:
        dp.appendleft(A[i])
    
    
    else:
        dp[ind-1] = A[i]

print(len(dp))

Solution (Python):
import bisect
from collections import deque

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

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

for i in range(1, N):
    ind = bisect.bisect_left(dp, A[i])

    if ind == 0:
        dp.appendleft(A[i])
    elif dp[-1] < A[i]:
        dp[-1] = A[i]
    else:
        dp[ind-1] = A[i]

print(len(dp))

Solution (Python):
from bisect import bisect_right
n = int(input())

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

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

print(ans)

Solution (Python):
ma = lambda :map(int,input().split())
lma = lambda :list(map(int,input().split()))
tma = lambda :tuple(map(int,input().split()))
ni = lambda:int(input())
yn = lambda fl:print("Yes") if fl else print("No")
import collections
import math
import itertools
import heapq as hq
n = ni()
A = []
for i in range(n):
    A.append(ni())
def isok(num,val):
    return num<val
def bisect(ls,val): 
    ok = -1
    ng = len(ls)
    x = (ok+ng)//2
    while ng-ok>1:
        num = ls[x]
        if isok(num,val):
            ok = x
        else:
            ng = x
        x = (ok+ng)//2
    return ok 
INF=10**10
prev=INF
ls =[-INF]*n+[INF]*n
idx=0
for a in A:
    if a>prev:
        pass
    else:
        idx=bisect(ls,a)
    ls[idx]=a
    
print(2*n-ls.count(INF)-ls.count(-INF))

Solution (Python):

from collections import defaultdict, deque, Counter, OrderedDict
from bisect import bisect_left, bisect_right
from functools import reduce, lru_cache
from heapq import heappush, heappop, heapify

import itertools
import math, fractions
import sys, copy

def L(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline().rstrip())
def SL(): return list(sys.stdin.readline().rstrip())
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI1(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return [list(x) for x in sys.stdin.readline().split()]
def R(n): return [sys.stdin.readline().strip() for _ in range(n)]
def LR(n): return [L() for _ in range(n)]
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def LIR1(n): return [LI1() for _ in range(n)]
def SR(n): return [SL() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]

def perm(n, r): return math.factorial(n) // math.factorial(r)
def comb(n, r): return math.factorial(n) // (math.factorial(r) * math.factorial(n-r))

def make_list(n, *args, default=0): return [make_list(*args, default=default) for _ in range(n)] if len(args) > 0 else [default for _ in range(n)]

dire = [[1, 0], [0, 1], [-1, 0], [0, -1]]
dire8 = [[1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1], [0, -1], [1, -1]]
alphabets = "abcdefghijklmnopqrstuvwxyz"
ALPHABETS = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
MOD = 1000000007
INF = float("inf")

sys.setrecursionlimit(1000000)


class SegmentTree:
    
    
    
    def __init__(self, size, f=lambda x,y : x+y, default=0):
        self.size = 2**(size-1).bit_length() 
        self.default = default
        self.data = [default]*(self.size*2) 
        self.f = f

    def update(self, i, x):
        i += self.size
        self.data[i] = x
        while i > 0:
            i >>= 1
            self.data[i] = self.f(self.data[i*2], self.data[i*2+1])

    
    def query(self, l, r):
        l += self.size
        r += self.size
        lres, rres = self.default, self.default
        while l < r:
            if l & 1:
                lres = self.f(lres, self.data[l])
                l += 1

            if r & 1:
                r -= 1
                rres = self.f(self.data[r], rres) 
            l >>= 1
            r >>= 1
        res = self.f(lres, rres)
        return res


def main():
    N = I()
    A = IR(N)

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

    print(len(LDS))

if __name__ == '__main__':
    main()

Solution (Python):
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 I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return 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

  
  return len(l)


print(main())