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):
import sys
input = sys.stdin.readline
from bisect import bisect_left, bisect_right


def read():
    N = int(input().strip())
    A = [int(input().strip()) for _ in range(N)]
    return N, A


def solve(N, A, INF=10**9+1):
    
    
    dp = [INF for i in range(N)]
    for i in range(N):
        a = A[N-i-1]
        idx = bisect_right(dp, a)
        dp[idx] = a
    return bisect_right(dp, INF-1)


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))

Solution (Python):
import bisect

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

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

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

print(lis(A[::-1]))

Solution (Python):
from collections import deque
import bisect

N = int(input())

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

q = deque([A[0]])

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

print(len(q))

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 = 998244353






N = getN()
A = getArray(N)

ans = deque([A[0]])
for i in range(1, N):
    index = bisect_left(ans, A[i])
    if index == 0:
        ans.appendleft(A[i])
    else:
        ans[index - 1] = A[i]

print(len(ans))

Solution (Python):
n = int(input())
a = [(-1)*int(input()) for _ in range(n)]
dp = [10**18 for _ in range(n)]

import bisect
def lis(a):
	"""
	param a: list
	return: the length of Longest increasing subsequence
	(be careful that [list] seq is not the LIS, but its length is accurate LIS length.)
	"""
	seq = []
	tmp = 0
	for i in a:
		pos = bisect.bisect_right(seq, i)
		if tmp <= pos:
			seq.append(i)
			tmp += 1
		else:
			seq[pos] = i
	return tmp

print(lis(a))

Solution (Python):
import sys
from bisect import bisect_right

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, *A = map(int, read().split())

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

    print(len(vec))
    return


if __name__ == '__main__':
    main()

Solution (Python):
from random import random
from sys import setrecursionlimit

setrecursionlimit(10 ** 6)


class TreapNode:
    _value = None
    _priority = None
    _count = None
    _left = None
    _right = None

    def __init__(self, value):
        self._value = value
        self._priority = random()
        self._count = 1


def treap_rotate_right(n):
    l = n._left
    n._left = l._right
    l._right = n
    return l


def treap_rotate_left(n):
    r = n._right
    n._right = r._left
    r._left = n
    return r


def treap_insert(n, v):
    if n is None:
        return TreapNode(v)
    if n._value == v:
        n._count += 1
        return n
    if n._value > v:
        n._left = treap_insert(n._left, v)
        if n._priority > n._left._priority:
            n = treap_rotate_right(n)
    else:
        n._right = treap_insert(n._right, v)
        if n._priority > n._right._priority:
            n = treap_rotate_left(n)
    return n


def treap_delete(n, v):
    if n is None:
        raise Exception('no nodes')
    if n._value > v:
        n._left = treap_delete(n._left, v)
        return n
    if n._value < v:
        n._right = treap_delete(n._right, v)
        return n

    
    if n._count > 1:
        n._count -= 1
        return n

    if n._left is None and n._right is None:
        return None

    if n._left is None:
        n = treap_rotate_left(n)
    elif n._right is None:
        n = treap_rotate_right(n)
    else:
        
        if n._left._priority < n._right._priority:
            n = treap_rotate_right(n)
        else:
            n = treap_rotate_left(n)
    return treap_delete(n, v)


def treap_size(n):
    if n is None:
        return 0
    return n._count + treap_size(n._left) + treap_size(n._right)


def treap_str(n):
    if n is None:
        return ""
    result = []
    if n._left is not None:
        result.append(treap_str(n._left))
    result.append("%d:%d" % (n._value, n._count))
    if n._right is not None:
        result.append(treap_str(n._right))
    return ' '.join(result)


def treap_search(n, v):
    
    if n is None:
        return None
    if n._value >= v:
        if n._left is None:
            return None
        return treap_search(n._left, v)
    
    if n._right is None:
        return n
    r = treap_search(n._right, v)
    if r is None:
        return n
    return r


class Treap:
    _root = None
    _size = 0

    def insert(self, v):
        self._root = treap_insert(self._root, v)
        self._size += 1

    def delete(self, v):
        self._root = treap_delete(self._root, v)
        self._size -= 1

    def __len__(self):
        return self._size

    def __str__(self):
        return treap_str(self._root)

    def search(self, v):
        return treap_search(self._root, v)


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

t = Treap()
for a in A:
    n = t.search(a)
    if n is not None:
        t.delete(n._value)
    t.insert(a)
print(len(t))

Solution (Python):
from bisect import bisect_right

N = int(input())
A = [int(input()) for i in range(0,N,1)]

maxs = []

for i in range(0,N,1):
    to_insert = bisect_right(maxs,-A[i])
    if len(maxs)==0:
        maxs.insert(0,-A[i])
    else:
        if to_insert < len(maxs):
            maxs[to_insert]=-A[i]
        else:
            maxs.append(-A[i])

print(len(maxs))

Solution (Python):


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

Solution (Python):
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

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

from bisect import bisect_right
lis = [1]
for a in As:
    if a>=lis[-1]:
        lis.append(a)
    else:
        lis[bisect_right(lis, a)] = a

print(len(lis))

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

L = [A[0]]
for i in range(1,N):
  if L[-1] >= A[i]:
    L.append(A[i])
  else:
    if L[0] < A[i]:
      L[0] = A[i]
    else:
      s = len(L)
      ok = s
      ng = 0
      while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if L[mid] < A[i]:
          ok = mid
        else:
          ng = mid
      L[ok] = A[i]
  
ans = len(L)
print(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):
import sys



from bisect import bisect_left, bisect_right





input = sys.stdin.readline

getS = lambda: input().strip()
getN = lambda: int(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__":
    
    solve()

Solution (Python):

import sys
from bisect import bisect_left
from bisect import bisect_right

INF = float("inf")


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

    dp = [INF]*N
    for i in range(N):
        j = bisect_right(dp, -A[i])
        dp[j] = -A[i]

    print(bisect_left(dp, INF))


if __name__ == '__main__':
    main()

Solution (Python):

import sys
from bisect import bisect_right

INF = float("inf")


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

    dp = [INF]*N
    for i in range(N):
        j = bisect_right(dp, -A[i])
        dp[j] = -A[i]

    print(sum([1 for d in dp if d < INF]))
    


if __name__ == '__main__':
    main()

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

def main():
  N = int(input())
  ans = 1
  lis_min = [int(input())]
  for i in range(N-1):
    a = int(input())
    index = bisect_right_reverse(lis_min, a)
    if index != len(lis_min):
      lis_min[index] = a
    else:
      ans += 1
      lis_min.append(a)
  print(ans)
if __name__ == "__main__":
  main()

Solution (Python):
from random import random
from sys import setrecursionlimit

setrecursionlimit(10 ** 5)


class TreapNode:
    _value = None
    _priority = None
    _count = None
    _left = None
    _right = None

    def __init__(self, value):
        self._value = value
        self._priority = random()
        self._count = 1


def treap_rotate_right(n):
    l = n._left
    n._left = l._right
    l._right = n
    return l


def treap_rotate_left(n):
    r = n._right
    n._right = r._left
    r._left = n
    return r


def treap_insert(n, v):
    if n is None:
        return TreapNode(v)
    if n._value == v:
        n._count += 1
        return n
    if n._value > v:
        n._left = treap_insert(n._left, v)
        if n._priority > n._left._priority:
            n = treap_rotate_right(n)
    else:
        n._right = treap_insert(n._right, v)
        if n._priority > n._right._priority:
            n = treap_rotate_left(n)
    return n


def treap_delete(n, v):
    if n is None:
        raise Exception('no nodes')
    if n._value > v:
        n._left = treap_delete(n._left, v)
        return n
    if n._value < v:
        n._right = treap_delete(n._right, v)
        return n

    
    if n._count > 1:
        n._count -= 1
        return n

    if n._left is None and n._right is None:
        return None

    if n._left is None:
        n = treap_rotate_left(n)
    elif n._right is None:
        n = treap_rotate_right(n)
    else:
        
        if n._left._priority < n._right._priority:
            n = treap_rotate_right(n)
        else:
            n = treap_rotate_left(n)
    return treap_delete(n, v)


def treap_size(n):
    if n is None:
        return 0
    return n._count + treap_size(n._left) + treap_size(n._right)


def treap_str(n):
    if n is None:
        return ""
    result = []
    if n._left is not None:
        result.append(treap_str(n._left))
    result.append("%d:%d" % (n._value, n._count))
    if n._right is not None:
        result.append(treap_str(n._right))
    return ' '.join(result)


def treap_search(n, v):
    
    if n is None:
        return None
    if n._value >= v:
        if n._left is None:
            return None
        return treap_search(n._left, v)
    
    if n._right is None:
        return n
    r = treap_search(n._right, v)
    if r is None:
        return n
    return r


class Treap:
    _root = None
    _size = 0

    def insert(self, v):
        self._root = treap_insert(self._root, v)
        self._size += 1

    def delete(self, v):
        self._root = treap_delete(self._root, v)
        self._size -= 1

    def __len__(self):
        return self._size

    def __str__(self):
        return treap_str(self._root)

    def search(self, v):
        return treap_search(self._root, v)


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

t = Treap()
for a in A:
    n = t.search(a)
    if n is not None:
        t.delete(n._value)
    t.insert(a)
print(len(t))

Solution (Python):
import bisect






 
n = int(input())
li = [int(input()) for i in range(n)]
li = [-x for x in li]

X = []
X.append(li[0])

for i in range(1,n):
    idx = bisect.bisect_right(X,li[i])
    if idx==len(X):
        X.append(li[i])
    else:
        X[idx] = li[i]

print(len(X))

Solution (Python):
import sys
from bisect import bisect_right

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


def main():
    N, *A = map(int, read().split())

    vec = [INF] * N
    for a in reversed(A):
        vec[bisect_right(vec, a)] = a

    try:
        print(vec.index(INF))
    except:
        print(N)

    return


if __name__ == '__main__':
    main()

Solution (Python):
import sys
from bisect import bisect_right

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


def main():
    N, *A = map(int, read().split())

    vec = [INF] * N
    for a in reversed(A):
        vec[bisect_right(vec, a)] = a

    print(N - vec.count(INF))
    return


if __name__ == '__main__':
    main()

Solution (Python):
import sys
from bisect import bisect_right

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


def main():
    N, *A = map(int, read().split())

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

    print(len(vec))
    return


if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque
import bisect
import sys
sys.setrecursionlimit(10**9)


def main():
    N = int(input())
    X = deque()

    for _ in range(N):
        a = int(input())
        j = bisect.bisect_left(X,a)

        if j == 0:
            X.appendleft(a)
        else:
            X[j-1] = a


    print(len(X))


if __name__ == "__main__":
  main()

Solution (Python):

import bisect

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

LIS = [-1] * N
LIS[-1] = seq[0]

for i in range(1, len(seq)):
    LIS[bisect.bisect_left(LIS, seq[i]) - 1] = seq[i]
    

c = LIS.count(-1)
print(len(LIS) - c)

Solution (Python):
import bisect

n = int(input())
a = []

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

stack = [a[0]]

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

print(len(stack))

Solution (Python):
import sys
import bisect

input = lambda: sys.stdin.readline().rstrip()

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


def solve():

    LIS = [A[0]]
    for i in range(1, N):

        if A[i] >= LIS[-1]:
            LIS.append(A[i])
        else:
            LIS[bisect.bisect_right(LIS, A[i])] = A[i]

    ans = len(LIS)
    print(ans)


if __name__ == '__main__':
    solve()

Solution (Python):


from bisect import bisect_left
from collections import *

N = int(input())

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

LIS = deque([A[0]])
cnt = 0

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

print(len(LIS))

Solution (Python):
n=int(input())
a=[-int(input()) for i in range(n)]
from bisect import bisect_right
l=[]
for aa in a:
  idx=bisect_right(l,aa)
  if idx==len(l):
    l.append(aa)
  else:
    l[idx]=aa
print(len(l))

Solution (Python):
from bisect import bisect_right

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

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

ans = len(li)
print(ans)

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

n = int(input())
a = [int(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)

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

import bisect





color=[1]
lencolor=1
for aa in a:
    aa=-1*aa
    i=bisect.bisect_right(color, aa)
    if i==lencolor:
        color.append(aa)
        lencolor+=1
        
    else:
        color[i]=aa
        
    
print(lencolor)

Solution (Python):
import bisect
N = int(input())
A = []
for i in range(N):
    A.append(int(input()))
A = A[::-1]
S = [A[0]]
c = 1
for i in range(1, N):
    t = A[i]
    if t >= S[-1]:
        S.append(t)
        c += 1
    else:
        p = bisect.bisect_right(S, t)
        S[p] = t
print(c)

Solution (Python):
import bisect

N = int(input())
ans = 0
X = [int(input())for _ in range(N)]
A = []
for a in X[::-1]:
    if len(A) == 0:
        A.append(a)
    elif A[-1] <= a:
        A.append(a)
    else:
        i = bisect.bisect_right(A, a)
        A[i] = a

print(len(A))

Solution (Python):
from collections import deque
import bisect

def main():
    N = int(input())
    l = deque([])

    for i in range(N):
        a = int(input())
        if len(l) == 0 or a <= l[0]:
            l.appendleft(a)
        else:
            ind = bisect.bisect_left(l, a)
            l[ind-1] = a

    print(len(l))

if __name__ == "__main__":
    main()

Solution (Python):
import bisect
from collections import deque

n = int(input())

c = deque([])
for i in range(n):
    a = int(input())
    if i == 0:
        c.append(a)
    else:
        ind = bisect.bisect_left(c,a)
        if ind > 0:
            c[ind-1] = a
        else:
            c.appendleft(a)

print(len(c))

Solution (Python):
from bisect import bisect_right
n = int(input())
a_list = []
for i in range(n):
    a = int(input())
    a_list.append(a)
a_list.reverse()
l_list = [a_list[0]]
for i in range(1, n):
    a = a_list[i]
    if l_list[-1] <= a:
        l_list.append(a)
    else:
        index = bisect_right(l_list, a)
        l_list[index] = a
print(len(l_list))

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

Solution (Python):
import bisect
from collections import deque
N = int(input())
A = [int(input()) for _ in range(N)]
c = deque()
c.append(A[0])
for i in range(1, N):
    j = bisect.bisect_right(c, A[i]-1)
    if j == 0:
        c.appendleft(A[i])
    else:
        c[j-1] = A[i]
print(len(c))

Solution (Python):
import bisect
N=int(input())
A=[]
ans=0
for i in range(N):
    a=int(input())
    A.append(a)
cl=[A[-1]]
ans=1
for i in range(N-1)[::-1]:
    a=A[i]
    if a>=cl[-1]:
        cl.append(a)
        ans+=1
    else:
        b=bisect.bisect_right(cl,a)
        cl[b]=a
print(ans)

Solution (Python):
def main():
    import sys
    import bisect

    read = sys.stdin.buffer.read
    bisect_right = bisect.bisect_right

    N, *A = map(int, read().split())

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

    print(len(dp))
    return


if __name__ == '__main__':
    main()

Solution (Python):
def main():
    import sys
    import bisect

    read = sys.stdin.buffer.read
    bisect_right = bisect.bisect_right

    N, *A = map(int, read().split())

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

    print(len(dp))
    return


if __name__ == '__main__':
    main()

Solution (Python):
import sys
from bisect import bisect_right

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


def main():
    N, *A = map(int, read().split())

    dp = [A.pop()]
    for a in reversed(A):
        if a >= dp[-1]:
            dp.append(a)
        else:
            dp[bisect_right(dp, a)] = a

    print(len(dp))
    return


if __name__ == '__main__':
    main()

Solution (Python):
import sys
from bisect import bisect_right

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


def main():
    N, *A = map(int, read().split())

    dp = [A.pop()]
    for a in reversed(A):
        if a >= dp[-1]:
            dp.append(a)
        else:
            dp[bisect_right(dp, a)] = a

    print(len(dp))
    return


if __name__ == '__main__':
    main()

Solution (Python):
import sys
from bisect import bisect_right

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


def main():
    N, *A = map(int, read().split())

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

    print(len(dp))
    return


if __name__ == '__main__':
    main()

Solution (Python):
import sys
from bisect import bisect_right

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


def main():
    N, *A = map(int, read().split())

    A.reverse()

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

    print(len(dp))
    return


if __name__ == '__main__':
    main()

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

n = int(input())
colors_maxs = []

colors_maxs.append(int(input()) *(-1) )
for _ in range(n-1):
    a = int(input()) * (-1)
    if colors_maxs[-1] <= a:
        colors_maxs.append(a)
    else:
        ind = bisect.bisect_right(colors_maxs, a) 
        colors_maxs[ind] = a

print(len(colors_maxs))

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

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

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

Solution (Python):
n = int(raw_input())
ais = [int(raw_input()) for _ in range(n)]
tails = []
import bisect
for a in ais:
	if not(tails) or (tails[-1] >= a):
		tails.append(a)
	else:
		
		986643321
		lo,hi = 0, len(tails) - 1
		while(lo<hi):
			med= (lo + hi)/2
			if tails[med] < a:
				hi = med
			else:
				lo = med + 1
		tails[lo] = a
print len(tails)

Solution (Python):
from bisect import bisect_right as br
n = int(input())
a = [int(input()) for _ in range(n)][::-1]
INF = float("INF")
lst = [INF]*n
ans = 0
for i in range(n):
    l = br(lst,a[i])
    lst[l] = a[i]
    ans = max(l+1,ans)
print(ans)

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


def main():
    input = stdin.buffer.readline
    n = int(input())
    a = [int(input()) for _ in range(n)]
    ans = deque()
    for ai in a:
        idx = bisect_left(ans, ai)
        if idx == 0:
            ans.appendleft(ai)
        else:
            ans[idx - 1] = ai

    print(len(ans))


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()

Solution (Python):
import sys
from collections import Counter
from collections import deque
import heapq
import math
import fractions
import bisect
import itertools
def input(): return sys.stdin.readline().strip()
def mp(): return map(int,input().split())
def lmp(): return list(map(int,input().split()))

n=int(input())
l=deque([])
for i in range(n):
    a=int(input())
    ind=bisect.bisect_right(l,a-1)
    if ind==0:
        l.appendleft(a)
    else:
        l[ind-1]=a
print(len(l))

Solution (Python):
import sys
from collections import Counter
from collections import deque
import heapq
import math
import fractions
import bisect
import itertools
def input(): return sys.stdin.readline().strip()
def mp(): return map(int,input().split())
def lmp(): return list(map(int,input().split()))

n=int(input())
l=deque([])
for i in range(n):
    a=int(input())
    ind=bisect.bisect_right(l,a-1)
    if ind==0:
        l.appendleft(a)
    else:
        l[ind-1]=a
print(len(l))

Solution (Python):
import sys
input = sys.stdin.readline
def nibun_right(a, x):
 lo, hi = 0, len(a)
 while lo < hi:
  mid = (lo+hi)//2
  if x < a[mid]: hi = mid
  else: lo = mid+1
 return lo
def nibun_left(a, x):
 lo, hi = 0, len(a)
 while lo < hi:
  mid = (lo+hi)//2
  if a[mid] < x: lo = mid+1
  else: hi = mid
 return lo
N=int(input())
ans=[1]*N
for i in range(N):
 x=int(input())
 c=nibun_right(ans, -x)
 ans[c]=-x
c=nibun_left(ans, 1)
print(c)

Solution (Python):

import bisect
from array import array


def slow_solve(N, As):
    colors = []
    for a in As:
        if not colors:
            colors.append(a)
        else:
            if a <= colors[0]:
                colors.append(a)
            else:
                i = bisect.bisect_left(colors, a)
                colors[i-1] = a
        colors.sort()
        print(colors)
    return len(colors)


def solve(N, As):
    colors = array('I', [])
    for a in As:
        if not colors:
            colors.append(a)
        else:
            if a <= colors[0]:
                colors.insert(0, a)
            else:
                i = bisect.bisect_left(colors, a)
                colors[i - 1] = a
                j = i - 1
                while j + 1 < len(colors) and colors[j] > colors[j + 1]:
                    colors[j], colors[j + 1] = colors[j + 1], colors[j]
                    j += 1
        
    return len(colors)













if __name__ == "__main__":
    N = int(input())
    As = []
    [As.append(int(input())) for i in range(N)]
    print(solve(N, As))

Solution (Python):
import bisect

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

dp = [float("inf")] * (N+1)
dp[0] = -float("inf")
dp[1] = A[0]

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

for i in reversed(range(N+1)):
    if dp[i] < float("inf"):
        print(i)
        break

Solution (Python):
from bisect import bisect_left

N=int(input())

dp=[-2]*(N+1)
dp[N]=-1

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

print(N-bisect_left(dp,0)+1)