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 sys import stdin, setrecursionlimit
from bisect import bisect_left
from collections import deque

setrecursionlimit(10 ** 9)
INF = 1 << 60


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


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

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

    print(len(B))


if __name__ == '__main__':
    main()

Solution (Python):

import sys
sys.setrecursionlimit(10 ** 7)
read = sys.stdin.buffer.read
inp = sys.stdin.buffer.readline
def inpS(): return inp().rstrip().decode()
readlines = sys.stdin.buffer.readlines
MOD = 10**9+7
INF = 1<<60

from bisect import bisect_right, bisect_left
def resolve():
    N = int(input())
    A = [int(input()) for _ in range(N)][::-1]

    dp = [INF]*(N+1)
    for a in A:
        ind = bisect_right(dp, a)
        dp[ind] = a

    ans = bisect_left(dp, INF)
    print(ans)

if __name__ == "__main__":
    resolve()

Solution (Python):


def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
from collections import deque
from bisect import bisect_left

N = INT()
A = []

for _ in range(N):
    A.append(INT())

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

print(len(t))

Solution (Python):


import bisect

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

A.reverse()
INF = float('inf')
dp = [INF for _ in range(N)]

for a in A:
    target_index = bisect.bisect_right(dp, a)
    
    dp[target_index] = a


print(bisect.bisect_left(dp, INF))

Solution (Python):
import bisect
n = int(input())
a = [int(input()) for i in range(n)]
ans = 0
color = [a[n-1]]
for i in range(n-2,-1,-1):
    if a[i]>=color[-1]:
        color.append(a[i])
    else:
        x = bisect.bisect_right(color,a[i])
        color[x] = a[i]
print(len(color))

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

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

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

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

t = [A[0]]
for a in A[1:]:
    if t[-1] >= a:
        t.append(a)
        continue
    ok = len(t) - 1
    ng = -1
    while ok - ng > 1:
        m = (ok + ng) // 2
        if t[m] < a:
            ok = m
        else:
            ng = m
    t[ok] = a
print(len(t))

Solution (Python):

from collections import deque

n=int(input())
a=[]
for i in range(n):
    A=int(input())
    a.append(A)
l=deque([a[0]])
for i in range(1,n):
    if l[0]>=a[i]:
        l.appendleft(a[i])
    elif l[-1]<a[i]:
        l[-1]=a[i]
    else:
        p=0
        q=len(l)-1
        while q-p!=1:
            if l[(p+q)//2]>=a[i]:
                q=(p+q)//2
            else:
                p=(p+q)//2
        l[p]=a[i]
print(len(l))

Solution (Python):
n = int(input())

colors = []

for i in range(n):
  a = int(input())
  if i == 0:
    colors.append(a)
    continue
  if colors[-1] >= a:
    colors.append(a)
  elif a > colors[0]:
    colors[0] = a
  else:
    l, r = 0, len(colors)
    while r-l > 1:
      k = (r+l)//2
      if a > colors[k]:
        r = k
      else:
        l = k
    if a > colors[l]:
      colors[l] = a
    else:
      colors[r] = a

print(len(colors))

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

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


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


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

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

    print(len(color))


if __name__ == "__main__":
    main()

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

from bisect import bisect_left, bisect_right, bisect, insort_left, insort_right, insort

def solve(N,A):
    ans = 0
    lis = []
    for i in range(N):
        ind = bisect_right(lis,-A[i])
        if ind == len(lis):
            lis.append(-A[i])
        else:
            lis[ind] = -A[i]
    ans = len(lis)
    return ans
print(solve(N,A))

Solution (Python):
import sys
input = sys.stdin.readline
n = int(input())
if n == 1:
  print(1)
  exit()
  
chk = []
for i in range(n):
  a = int(input())
  chk.append(a)
  
from bisect import bisect_left,insort_left
from collections import deque
ans = 0

c = deque([])
for j in chk:
  if i == 0:
    c.append(j)
  else:
    ind = bisect_left(c,j)
    if ind == 0:
      ans += 1
      c.appendleft(j)
    else:
      c[ind-1] = (j)
      
print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
n = int(input())
if n == 1:
  print(1)
  exit()
  
chk = []
for i in range(n):
  a = int(input())
  chk.append((i,a))
  
from bisect import bisect_left,insort_left
from collections import deque
ans = 1

c = deque([])
for j in chk:
  i,a = j
  if i == 0:
    c.append((a,n-i))
  else:
    ind = bisect_left(c,(a,n-i))
    if ind == 0:
      ans += 1
      c.appendleft((a,n-i))
    else:
      c[ind-1] = (a,n-i)
      
print(ans)

Solution (Python):
import bisect

N = int(input())
LIS = [-1 * int(input())]
for _ in range(N-1):
    A = -1 * int(input())
    if A >= LIS[-1]:
        LIS.append(A)
    else:
        LIS[bisect.bisect_right(LIS, A)] = A

print(len(LIS))

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


LIS = deque([nums[0]])
count = 0
for index, num in enumerate(nums):
    if index == 0:
        continue
    if num <= LIS[0]:
        LIS.appendleft(num)
    else:
        insert_index = bisect.bisect_left(LIS, num)
        LIS[insert_index - 1] = num
print(len(LIS))

Solution (Python):

import sys
import bisect

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

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



def main():
    tokens = iterate_tokens()
    N = int(next(tokens))  
    solve(N)

if __name__ == '__main__':
    main()

Solution (Python):

from collections import deque
import bisect


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

d = deque()

for a in A:
    p = bisect.bisect_left(d, a)
    if p == 0:
        d.appendleft(a)
        continue
    d[p-1] = a

print(len(d))

Solution (Python):

import heapq
from collections import defaultdict, deque

from itertools import accumulate, permutations
import sys
import bisect


sys.setrecursionlimit(10 ** 7)
INF = float("inf")
MOD = 10 ** 9 + 7

si = lambda: input().strip()
ii = lambda: int(input())
mii = lambda: map(int, input().split())
msi = lambda: map(str, input().split())
lmii = lambda: list(map(int, input().split()))
lmsi = lambda: list(map(str, input().split()))
smii = lambda: sorted(map(int, input().split()))


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

d = deque()

for a in A:
    p = bisect.bisect_left(d, a)
    if p == 0:
        d.appendleft(a)
        continue
    d[p-1] = a

print(len(d))

Solution (Python):
n=int(input())
A=[int(input()) for i in range(n)]
l=[-A[0],1]
from bisect import *
for a in A[1:]:
    idx=bisect_left(l,-a+1)
    p=-l[idx]
    if p==-1:
        l[-1]=-a
        l.append(1)
    else:
        l[idx]=-a
print(len(l)-1)

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

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

print(len(que))

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



def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def LI(): return list(map(int,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([A[0]])
	
	for i in range(1,n):
		if A[i]<=Q[0]:
			Q.appendleft(A[i])
		else:
			a=bisect.bisect_left(Q,A[i])
			Q[a-1]=A[i]
	print(len(Q))








if __name__ == "__main__":
	main()

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



def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def LI(): return list(map(int,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([A[0]])
	
	for i in range(1,n):
		if A[i]<=Q[0]:
			Q.appendleft(A[i])
		else:
			a=bisect.bisect_left(Q,A[i])
			Q[a-1]=A[i]
	print(len(Q))








if __name__ == "__main__":
	main()

Solution (Python):
import bisect

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


colors = []
for i in reversed(range(N)):
    if i == N-1:
        colors.append(A[i])
    else:
        if A[i] >= colors[-1]:
            colors.append(A[i])
        
        else:
            idx = bisect.bisect_right(colors, A[i])
            colors[idx] = A[i]


print(len(colors))

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

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
infi = 10 ** 20


n, *A = map(int, read().split())
LIS = deque([10 ** 10])
for a in A:
    a *= -1
    pos1 = bisect_left(LIS, a)
    pos2 = bisect_right(LIS, a)
    if LIS[-1] <= a:
        LIS.append(a)
    else:
        if LIS[pos1] == a:
            LIS[pos2] = a
        else:
            LIS[pos1] = a

print(len(LIS))

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

INF = float('inf')

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

def getLenLNDS(As):
    dp = [-INF]
    for A in As:
        if dp[-1] <= A:
            dp.append(A)
        else:
            i = bisect_right(dp, A)
            dp[i] = A
    return len(dp)-1

ans = getLenLNDS(As)

print(ans)

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

print(len(b))

Solution (Python):

import sys
from bisect import bisect_left,bisect_right
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    N=int(input())
    A=[-int(input()) for i in range(N)]
    dp=[INF]*(N+2)
    dp[0]=-INF
    for i in range(N):
        dp[bisect_right(dp,A[i])]=A[i]
    for i in range(N+2):
        if dp[i]==INF:
            print(i-1)
            exit()

if __name__ == '__main__':
    main()

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

Solution (Python):


import sys



















def main():
    mod = 1000000007                  
    inf = float('inf')
    sys.setrecursionlimit(10**6)    
    def input(): return sys.stdin.readline().rstrip()
    def ii():  return int(input())
    def mi():  return map(int, input().split())
    def mi_0(): return map(lambda x: int(x)-1, input().split())
    def lmi(): return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():  return list(input())
    

    def reverse_bisect(L, key):
        """
        L は単調減少
        key 未満となる最初の index を返す
        - left は常に key 未満の条件を満たさない
        - right は常に key 未満の条件を満たす
        - right - left で表される区間幅が 1 になるまで狭める。right が答えになる。
        """
        left = -1
        right = len(L)
        while right - left > 1:
            mid = left + (right - left) // 2
            if L[mid] < key:
                right = mid
            else:
                left = mid
        return right

    
    
    n = ii()
    L = [ii() for _ in range(n)]
    
    
    dp = [-float('inf')] * n
    for elm in L:
        insert_ind = reverse_bisect(dp, elm)
        dp[insert_ind] = elm

    prev = -1
    for i, tail_max in enumerate(dp):
        if tail_max == -float('inf'):
            
            break
        prev = i
    print(prev + 1)



if __name__ == "__main__":
    main()

Solution (Python):
N = int(input())
A = [int(input()) for _ in range(N)][::-1]
def LIS(L):
  from bisect import bisect
  seq=[]
  for i in L:
    pos=bisect(seq,i)
    if len(seq)<=pos:
      seq.append(i)
    else:
      seq[pos]=i
  return len(seq)
print(LIS(A))

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

def main():
    N = int(input())
    INF = 10**10
    col = deque([INF])
    for _ in range(N):
        num = int(input())
        ind = bisect.bisect_left(col,num)
        if ind == 0:
            col.appendleft(num)
        else:
            col[ind-1] = num
    
    print(len(col)-1)

if __name__ == "__main__":
    main()

Solution (Python):
import bisect
N=int(input())

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


color_list=[alist.pop()]
for i in reversed(range(N-1)):
  a=alist[i]
  if a>=color_list[-1]:
    
    color_list.append(a)
  else:
    
    pos=bisect.bisect(color_list,a)
    color_list[pos]=a
  
  
print(len(color_list))

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 DP[-1]<=num:
        DP.append(num)
    else:
        index=bisect_right(DP,num)
        DP[index]=num
print(len(DP))

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

from bisect import bisect_left, bisect_right

n = int(readline())
a = [int(readline()) for _ in range(n)]
inf = float('inf')
memo = [inf] * n
for aa in a[::-1]:
    memo[bisect_right(memo, aa)] = aa
print(bisect_left(memo, inf))

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

Solution (Python):
import sys

input = sys.stdin.readline
import bisect

INF = 10 ** 18
N = int(input())
A = [10 ** 10 - int(input()) for _ in range(N)]  



dp = [INF] * (N + 1)  

for a in A:
    idx = bisect.bisect_right(dp, a)
    dp[idx] = a

answer = bisect.bisect_left(dp, INF)
print(answer)

Solution (Python):
import bisect
from collections import deque
n = int(input())
color = [-1]*n

for i in range(n):
    a = int(input())
    color[bisect.bisect_left(color,a) - 1] = a

ans = n - bisect.bisect_right(color,-1)
print(ans)

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

def main():
    N = int(input())
    counter = deque([])
    for _ in range(N):
        a = int(input())
        ind = bisect_left(counter, a)
        if ind == 0:
            counter.appendleft(a)
        else:
            counter[ind-1] = a
    print(len(counter))


if __name__ == '__main__':
    main()

Solution (Python):

import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

n = int(input())
A = [int(input()) for i in range(n)]
dp = [-inf] * (10**5+10);dp[-1] = inf
for ai in A:
  dp[bisect.bisect_left(dp,ai)-1] = ai
for di in dp:
  if di != -inf:ans += 1
print(ans - 1)

Solution (Python):
import bisect
import sys
input = sys.stdin.readline
N = int(input())
A = []
for n in range(N):
    A.append(int(input()))
A = A[::-1]
INF = int(1e+9 + 10)
lis = [INF] * N
for n in range(N):
    i = bisect.bisect(lis, A[n])    
    lis[i] = A[n]
print (bisect.bisect_left(lis, INF))

Solution (Python):
import bisect
import sys
input = sys.stdin.readline
N = int(input())
A = []
for n in range(N):
    A.append(int(input()))
A = A[::-1]
INF = int(1e+9 + 10)
lis = [INF]* (N+1)
lis[0] = -1
for n in range(N):
    i = bisect.bisect(lis, A[n])    
    lis[i] = A[n]
print (bisect.bisect_left(lis, INF) - 1)

Solution (Python):
from bisect import bisect_right

N = int(input())
A = [int(input()) for _ in range(N)]
INF = 10**18

dp = [INF] * N
for a in A:
    dp[bisect_right(dp, -a)] = -a
ans = N - dp.count(INF)
print(ans)

Solution (Python):
from random import random


class TreapNode():
    """Treapが保持するノードを定義する。
    ノードは値と優先度、および親と子へのポインタを持つ。"""
    def __init__(self, val):
        self.val = val
        self.priority = random()
        self.parent, self.right, self.left = None, None, None

class Treap():
    def __init__(self, multiset=True):
        self.root = None

    def search(self, val: int) -> bool:
        """集合に値valを持つノードが存在するかどうかを返す。"""
        ptr = self.root
        while ptr is not None:
            if ptr.val == val:
                return True
            if val < ptr.val:
                ptr = ptr.left
            else:
                ptr = ptr.right
        return False

    def insert(self, val: int) -> bool:
        """集合に値valを持つノードを挿入する。
        挿入に成功したときTrue、失敗したときにFalseを返す。"""
        if self.root is None:
            self.root = TreapNode(val)
            return True

        
        ptr = self.root 
        while True:
            if val < ptr.val:
                if ptr.left is None:
                    ptr.left = TreapNode(val)
                    ptr.left.parent = ptr
                    ptr = ptr.left
                    break
                ptr = ptr.left
            else:
                if ptr.right is None:
                    ptr.right = TreapNode(val)
                    ptr.right.parent = ptr
                    ptr = ptr.right
                    break
                ptr = ptr.right

        
        while (ptr.parent is not None) and (ptr.parent.priority > ptr.priority):
            if ptr.parent.right == ptr:
                self.rotate_left(ptr.parent)
            else:
                self.rotate_right(ptr.parent)
        if ptr.parent is None:
            self.root = ptr 
        return True

    def delete(self, val: int) -> True:
        """集合から値valを持つノードを削除する。
        削除に成功したときTrue、失敗したときにFalseを返す。"""
        if self.root is None:
            return False

        ptr = self.root         
        while True: 
            if ptr is None:
                return False
            if ptr.val == val:
                break
            elif val < ptr.val:
                ptr = ptr.left
            else:
                ptr = ptr.right

        
        while (ptr.left is not None) or (ptr.right is not None):
            if ptr.left is None:
                self.rotate_left(ptr)
            elif ptr.right is None:
                self.rotate_right(ptr)
            elif ptr.left.priority < ptr.right.priority:
                self.rotate_right(ptr)
            else:
                self.rotate_left(ptr)
            if self.root == ptr:
                self.root = ptr.parent

        
        if ptr.left is None and ptr.right is None:
            if ptr == self.root:
                self.root = None
            elif ptr.parent.left == ptr:
                ptr.parent.left = None
            else:
                ptr.parent.right = None      
        return True

    def rotate_left(self, ptr):
        """木の左回転を行う"""
        w = ptr.right
        w.parent = ptr.parent
        if w.parent is not None:
            if w.parent.left == ptr:
                w.parent.left = w
            else:
                w.parent.right = w
        ptr.right = w.left
        if ptr.right is not None:
            ptr.right.parent = ptr
        ptr.parent = w
        w.left = ptr
        if ptr == self.root:
            self.root = w
            self.root.parent = None

    def rotate_right(self, ptr):
        """木の右回転を行う"""
        w = ptr.left
        w.parent = ptr.parent
        if w.parent is not None:
            if w.parent.right == ptr:
                w.parent.right = w
            else:
                w.parent.left = w
        ptr.left = w.right
        if ptr.left is not None:
            ptr.left.parent = ptr
        ptr.parent = w
        w.right = ptr
        if ptr == self.root:
            self.root = w
            self.root.parent = None

    def search_less_than(self, val):
        if val == None:
            return None
        ptr = self.root
        ret = None
        while ptr is not None:
            if ptr.val >= val:
                ptr = ptr.left
            else:
                ret = ptr.val
                ptr = ptr.right
        return ret

n = int(input())
a = [int(input()) for i in range(n)]
tp = Treap()
cnt = 0
for i in range(n):
    num = tp.search_less_than(a[i])
    if num is None:
        tp.insert(a[i])
        cnt += 1
    else:
        tp.delete(num)
        tp.insert(a[i])
print(cnt)

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

B = []
import bisect
for i, a in enumerate(A):
    if len(B) == 0:
        B.append(-a)
    else:
        j = bisect.bisect_right(B, -a)
        
        if j == len(B):
            B.append(-a)
        elif j == 0:
            B[0] = -a
        else:
            B[j] = -a
    

print(len(B))

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

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

Solution (Python):

from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.buffer.readline().split()]
def I(): return int(sys.stdin.buffer.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n = I()
    a = IR(n)
    dp = [float("inf")]*n
    for i in a:
        j = bisect.bisect_right(dp,-i)
        dp[j] = -i
    print(n-dp.count(float("inf")))
    return


if __name__ == "__main__":
    solve()

Solution (Python):
def binary_search(c1, c2):
    m = (c1 + c2 + 1) // 2
    if abs(c1 - c2) <= 1:
        return m
    else:
        if dp[m] < a:
            c1 = m
        else:
            c2 = m
        return binary_search(c1, c2)

n = int(input())
dp = [-1 for _ in range(n)]
for _ in range(n):
    a = int(input())
    m = binary_search(n - 1, -1)
    dp[m] = a
ans = 0
for i in dp:
    if i == -1:
        break
    else:
        ans += 1
print(ans)

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

Solution (Python):

from collections import deque
import bisect
n = int(input())
a = [int(input()) for _ in range(n)]
result = deque()

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

Solution (Python):
import sys
from bisect import bisect_right as bi_r, bisect_left as bi_l
inf = float('inf')

n, *a = map(int, sys.stdin.read().split())

def main():
  res = [inf] * n
  for x in a[::-1]:
    res[bi_r(res, x)] = x
  print(bi_l(res, inf))

if __name__ == '__main__':
  main()

Solution (Python):
import sys
from bisect import bisect_right as bi_r, bisect_left as bi_l
inf = float('inf')

n, *a = map(int, sys.stdin.read().split())

def main():
  res = [inf] * n
  for x in a[::-1]:
    res[bi_r(res, x)] = x
  print(bi_l(res, inf))

if __name__ == '__main__':
  main()

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

resolve()

Solution (Python):
def resolve():
    import bisect
    n = int(input())
    a = [int(input()) for _ in range(n)]
    m = []
    for i in range(n-1, -1, -1):
        if i == n-1:
            m.append(a[i])
        else:
            if m[-1] <= a[i]:
                m.append(a[i])
            elif m[0] > a[i]:
                m[0] = a[i]
            else:
                j = bisect.bisect_right(m, a[i])
                m[j] = a[i]
    print(len(m))
resolve()

Solution (Python):

"""
与えられたリストを反転した場合の広義(重複を許した)LIS(最長増加部分列)
の長さが答え。
"""
import bisect
import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0


lst1 = []
n = int(readline())
for i in range(n):
    lst1.append(int(readline()))

lst1.reverse() 

def LIS(lst):
    dp=[]
    for i in lst:
        pos=bisect.bisect_right(dp,i) 
        if len(dp)<=pos:
            dp.append(i)
        else:
            dp[pos]=i
    return len(dp)

print(LIS(lst1))

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

n = int(input())
max_color = deque([int(input())])
for _ in range(n-1):
  a = int(input())
  if a <= max_color[0]:
    max_color.appendleft(a)
  else:
    index = bisect_left(max_color, a) - 1
    max_color[index] = a
print(len(max_color))

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

import bisect

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

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

print(len(a))

Solution (Python):
import sys
import bisect

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


if __name__ == '__main__':
    solve()

Solution (Python):
import bisect
N=int(input())
A=[int(input()) for _ in range(N)]
color=[-1]*(N)
for a in A:
    i=bisect.bisect_left(color,a)
    color[i-1]=a
print(N-bisect.bisect_right(color,-1))

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

Solution (Python):
from bisect import bisect_left, bisect_right

N = int(input())

color = []
color.append(int(input()))

for i in range(N-1):
  A = int(input())
  
  if color[-1] >= A:
    color.append(A)

  else:
    color.reverse()
    l = bisect_left(color,A)
    color[l-1] = A
    color.reverse()


print(len(color))

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


def LIS(seq: list) -> int:
    """param: seq
    return:LISの長さ（a_i =< a_j）
    """
    from bisect import bisect_right
    N = len(seq)
    L = [seq[0]]
    for i in range(1, N):
        if seq[i] > L[-1]:
            L.append(seq[i])
        else:
            idx = bisect_right(L, seq[i])
            if idx == len(L):
                L.append(None)  
            L[idx] = seq[i]
    return len(L)


print(LIS(A))

Solution (Python):


from bisect import *



def resolve():
    N = int(input())
    A = [int(input()) for i in range(N)]
    A.reverse()

    B =[A[0]]

    A=A[1:]
    for  i in A:
        if i >= B[-1]:
            B.append(i)
            continue
        point = bisect_right(B,i)
        B[point]=i

    print(len(B))
if __name__ == "__main__":
    resolve()

Solution (Python):

import bisect
from collections import deque

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

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

ans = len(que)
print(ans)

Solution (Python):
import bisect

f_inf = float("inf")
n = int(input())
A = [int(input()) for _ in range(n)][::-1]
dp = [f_inf for _ in range(n + 1)]

for a in A:
    idx = bisect.bisect_right(dp, a)
    dp[idx] = a

ans = bisect.bisect_left(dp, f_inf)
print(ans)

Solution (Python):
def main():
    from heapq import heappop, heappush
    import sys

    input = sys.stdin.readline

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

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

    b = [-1]
    for x in a:
        i = binary_search(b, x)
        if i == len(b):
            b.append(x)
        else:
            b[i] = x

    ans = len(b)

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import bisect
n = int(input())
A = [int(input()) for i in range(n)]
m = 10**9
X = []
for a in A:
    i = bisect.bisect_right(X, -a)
    if i == len(X):
        X.append(-a)
    else:
        X[i] = -a
print(len(X))

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


def LIS(seq, wider_sense=False):
    from bisect import bisect_left, bisect_right
    f = bisect_right if wider_sense else bisect_left
    N = len(seq)
    INF = 10**18
    dp = [INF] * (N+1)
    for x in seq:
        i = f(dp, x)
        dp[i] = x
    return f(dp, INF-1)


answer = LIS(A, wider_sense=True)
print(answer)