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 bisect
from collections import deque
N = int(input())
ans = deque()

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

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

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

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


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

Solution (Python):
def examA():
    N, M = LI()
    l = 1; r = N
    for _ in range(M):
        L, R = LI()
        l = max(L,l)
        r = min(R,r)
    ans = max(0,r-l+1)
    print(ans)
    return

def examB():
    N = I()
    S = [I()for _ in range(N)]
    rest = []
    for s in S:
        if s%10==0:
            continue
        rest.append(s)
    if sum(S)%10==0:
        if not rest:
            print(0)
            return
        ans = sum(S) - min(rest)
    else:
        ans = sum(S)
    print(ans)
    return

def examC():
    N, K = LI()
    K -= 1
    A = LI()
    L = A.index(1)
    
    ans = (N-1+K-1)//K
    print(ans)
    return

def examD():
    def ketadp(a):
        n = len(a)
        dp = defaultdict(int)
        dp[0, 0, 0, 0, 0] = 1
        for i, less, has3, has5, has7 in itertools.product(range(n), (0, 1), (0, 1), (0,1), (0,1)):
            max_d = 7 if less else int(a[i])
            for d in range(max_d + 1):
                if d==0 and has3==0 and has5==0 and has7==0:
                    dp[i + 1, 1, has3, has5, has7] += dp[i, less, has3, has5, has7]
                if not (d==3 or d==5 or d==7):
                    continue
                less_ = less or d < max_d
                has3_ = has3 or d == 3
                has5_ = has5 or d == 5
                has7_ = has7 or d == 7
                dp[i + 1, less_, has3_, has5_, has7_] += dp[i, less, has3, has5, has7]

        ans = sum(dp[n, less, 1, 1, 1] for less in (0, 1))
        return ans
    N = SI()
    ans = ketadp(N)
    print(ans)
    return

def examE():
    N = I()
    A = [I()for _ in range(N)]
    que = deque()
    que.append(A[0])
    for a in A[1:]:
        cur = bisect.bisect_left(que,a)
        if cur==0:
            que.appendleft(a)
        else:
            que[cur-1] = a
    ans = len(que)
    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(readline())
def LI(): return list(map(int,readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examE()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn
"""

Solution (Python):
import bisect
from collections import deque

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


dp = deque([seq[0]])

for i in range(1,len(seq)):
    if seq[i] <= dp[0]:
        dp.appendleft(seq[i])

    else:
        dp[bisect.bisect_left(dp, seq[i])-1] = seq[i]

print(len(dp))

Solution (Python):
import bisect
from collections import deque

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

d = deque()
d.append(a[-1])
for i in reversed(range(N-1)):
	if a[i] >= d[-1]:
		d.append(a[i])
	else:
		index = bisect.bisect_right(d,a[i])
		d[index] = a[i]

print(len(d))

Solution (Python):
import bisect
from collections import deque

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

LIS = deque([a[0]])
for i in range(1,N):
    if a[i] > LIS[-1]:
    	LIS[-1] = a[i]
    elif LIS[0] >= a[i]:
    	LIS.appendleft(a[i])
    else:
    	LIS[bisect.bisect_left(LIS, a[i])-1] = a[i]

print(len(LIS))

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

def binsearch(threshold, lst):
    left, right = -1, len(lst)
    while right - left > 1:
        mid = (left + right) // 2
        if lst[mid] < threshold:
            right = mid
        else:
            left = mid
    return right


last=[]
for val in A:
    temp = binsearch(val, last)
    if temp == len(last):
        
        last.append(val)
    else:
        last[temp] = val
    
print(len(last))

Solution (Python):
from collections import deque
import bisect

N = int(input())
L = [int(input()) for _ in range(N)]
Q = deque()
Q.append(L[0])

for l in L[1:]:
    r = bisect.bisect_left(Q, l)
    if r == 0:
        Q.appendleft(l)
    else:
        Q[r-1] = l
print(len(Q))

Solution (Python):
import bisect

n = int(input())

c = []
for i in range(n):
    a = int(input())
    j = bisect.bisect_right(c, -a)
    if j == len(c):
        c.append(-a)
    else:
        c[j] = -a
print(len(c))

Solution (Python):
def sub():
  import sys
  input = sys.stdin.readline
  n = int(input())
  a1 = int(input())
  a = [a1]
  ap = a.append
  for _ in range(n-1):
    ai = int(input())
    if ai <= a[-1]:
      ap(ai)
    elif ai > a[0]:
      a[0] = ai
    else:
      h = 0
      l = len(a)-1
      while l-h>1:
        m = (l+h)//2
        if ai > a[m]:
          l = m
        else:
          h = m
      a[l] = ai
  print(len(a))   
sub()

Solution (Python):
from bisect import bisect_right

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

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

print(max(i + 1 for i, v in enumerate(dp) if v < INF))

Solution (Python):
mod = 10 ** 9 + 7
mod2 = 2**61+1
from collections import deque
import heapq
from bisect import bisect_left, insort_left, bisect_right

def iip(listed):
    ret = [int(i) for i in input().split()]
    if len(ret) == 1 and not listed:
        return ret[0]
    return ret

def iip_ord():
    return [ord(i) - ord("a") for i in input()]


def main():
    ans = solve()
    if ans is not None:
        print(ans)

def solve():
    N = iip(False)
    A = []
    for i in range(N):
        A.append(iip(False))

    maxes = [1]
    nc = 1
    for a in A:
        idx = bisect_right(maxes, -a)
        
        
        if idx == nc:
            maxes.append(-a)
            nc += 1
        else:
            maxes[idx] = -a

    print(nc)



def split_print_space(s):
    print(" ".join([str(i) for i in s]))


def split_print_enter(s):
    print("\n".join([str(i) for i in s]))


def koenai_saidai_x_index(sorted_list, n):
    l = 0
    r = len(sorted_list)
    if len(sorted_list) == 0:
        return False
    if sorted_list[0] > n:
        return False

    while r - l > 1:
        x = (l + r) // 2
        if sorted_list[x] == n:
            return x
        elif sorted_list[x] > n:
            r = x
        else:
            l = x
    return l


def searchsorted(sorted_list, n, side):
    if side not in ["right", "left"]:
        raise Exception("sideはrightかleftで指定してください")

    l = 0
    r = len(sorted_list)

    if n > sorted_list[-1]:
        
        return len(sorted_list)
    if n < sorted_list[0]:
        return 0

    while r - l > 1:
        x = (l + r) // 2
        if sorted_list[x] > n:
            r = x
        elif sorted_list[x] < n:
            l = x
        else:
            if side == "left":
                r = x
            elif side == "right":
                l = x

    if side == "left":
        if sorted_list[l] == n:
            return r - 1
        else:
            return r

    if side == "right":
        if sorted_list[l] == n:
            return l + 1
        else:
            return l


def soinsuu_bunkai(n):
    ret = []
    for i in range(2, int(n ** 0.5) + 1):
        while n % i == 0:
            n //= i
            ret.append(i)
        if i > n:
            break
    if n != 1:
        ret.append(n)
    return ret


def conbination(n, r, mod, test=False):
    if n <= 0:
        return 0
    if r == 0:
        return 1
    if r < 0:
        return 0
    if r == 1:
        return n
    ret = 1
    for i in range(n - r + 1, n + 1):
        ret *= i
        ret = ret % mod

    bunbo = 1
    for i in range(1, r + 1):
        bunbo *= i
        bunbo = bunbo % mod

    ret = (ret * inv(bunbo, mod)) % mod
    if test:
        
        pass
    return ret


def inv(n, mod):
    return power(n, mod - 2)


def power(n, p, mod_= mod):
    if p == 0:
        return 1
    if p % 2 == 0:
        return (power(n, p // 2, mod_) ** 2) % mod_
    if p % 2 == 1:
        return (n * power(n, p - 1, mod_)) % mod_


if __name__ == "__main__":
    main()

Solution (Python):

import sys
import math
import string
import collections
import fractions
import random
from operator import itemgetter
import itertools
from collections import deque
import copy
import heapq
import bisect

MOD = 10 ** 9 + 7
INF = float('inf')
input = lambda: sys.stdin.readline().strip()

sys.setrecursionlimit(10 ** 8)

N = int(input())
A = [int(input()) for _ in range(N)]
Min = [A[-1]]
for i in range(N - 2, -1, -1):
    temp = bisect.bisect_right(Min, A[i])
    if temp == len(Min):
        Min.append(A[i])
    elif Min[temp] != A[i]:
        Min[temp] = A[i]
    elif temp + 1 != len(Min):
        Min[temp + 1] = A[i]
    else:
        Min.append(A[i])
print(len(Min))

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

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

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

Solution (Python):



import bisect
n = int(input())
lists = [int(input()) for _ in range(n)]
lists = lists[::-1]
dataset = []
dataset.append(lists[0])

for i in range(1, n):
    x = lists[i]
    if x >= dataset[-1]:
        dataset.append(x)
    elif x < dataset[-1]:
        index = bisect.bisect_right(dataset, x)
        dataset[index] = x
print(len(dataset))

Solution (Python):
from bisect import bisect_right
N = int(input())
A = [int(input()) for _ in range(N)]
dp = [10**10] * N
for a in A:
    a = -a
    dp[bisect_right(dp, a)] = a
ans = N - dp.count(10**10)
print(ans)

Solution (Python):
n=int(input())
a=[int(input())*(-1) for _ in range(n)]
inf=10**10
l=[inf]*n
import bisect
for i in range(n):
	r=bisect.bisect_right(l,a[i])
	l[r]=a[i]
cnt=0
for i in range(n):
	if l[i]!=inf:
		cnt+=1
	else:
		break
print(cnt)

Solution (Python):
import sys

import bisect













readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    n = int(input())
    a = [-int(readline()) for _ in range(n)]

    c = [1] * n

    for number in a:
        idx = bisect.bisect_right(c, number)
        c[idx] = number

    ans = bisect.bisect_left(c, 1)
    print(ans)


if __name__ == '__main__':
    main()

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

import bisect

dp = [-1]*(n+1)

for i in range(n):
  v = int(input())
  l = bisect.bisect_left(dp, v)
  if l==n+1:
    l -= 1
  if dp[l]<v:
    dp[l] = v
  else:
    dp[l-1] = v

cnt = 0
for i in range(n, 0, -1):
  if dp[i]>=0:
    cnt += 1
  else:
    break
    
print(cnt)

Solution (Python):

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

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]

print(len(LIS))

Solution (Python):
'''
https://atcoder.jp/contests/abc134/tasks/abc134_e
'''
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    
    from itertools import combinations, permutations, accumulate
    
    from bisect import bisect_left,bisect_right
    import heapq
    from math import floor, ceil
    

    
    

    N = int(input())
    A = [int(input()) for _ in range(N)]
    d = deque()
    for i in A:
        pos = bisect_left(d, i)
        if pos == 0:
            d.appendleft(i)
        else:
            d[pos-1] = i
    print(len(d))

if __name__ == '__main__':
    main()

Solution (Python):
import bisect
from collections import deque

n = int(input())
la = [int(input()) for _ in range(n)]
result = deque([])

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

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

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

NUM = deque()
NUM.appendleft(A[0])

A = A[1:]


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


print(len(NUM))

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

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

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))


N = ir()
INF = 10 ** 12
dp = [INF] * (N+1)
for _ in range(N):
    a = ir()
    i = bisect_right(dp, -a)
    dp[i] = -a

print(bisect_left(dp, INF))

Solution (Python):
N=int(input())
ans=[]
m=10**10
for i in range(0,N):
    a=int(input())
    if m>=a:
        ans.append(a)
        m=a
    else:
        start=0
        end=len(ans)-1
        while end-start>1:
            test=(end+start)//2
            if a>ans[test]:
                end=test
            else:
                start=test
        if a>ans[start]:
            ans[start]=a
            if start==len(ans)-1:
                m=a
        else:
            ans[end]=a
            if end==len(ans)-1:
                m=a

print(len(ans))

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

Solution (Python):
n=int(input())
x=[int(input())]
for i in range(n-1):
  a=int(input())
  if x[-1]>=a:
    x+=[a]
  else:
    low=0
    high=len(x)-1
    mid=(high+low)//2
    while high-low>1:
      if x[mid]<a:
        high=mid
      else:
        low=mid
      mid=(high+low)//2
    if x[mid]<a:
      x[mid]=a
    else:
      x[high]=a
print(len(x))

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

Solution (Python):
import bisect

n = int(input())
a = [int(input()) for _ in range(n)]
r = [-1] * n
for a in a:
    i = bisect.bisect_left(r, a)
    r[i - 1] = a
print(len(r) - r.count(-1))

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

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

s = deque([a[0]])

from bisect import bisect_left

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


print(len(s))

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

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

dp = [10**10] * N

for a in A:
    a = -a
    dp[bisect_right(dp, a)] = a

ans = N - dp.count(10**10)
print(ans)

Solution (Python):
from collections import deque
import bisect
n = int(input())
L = deque([int(input())])
for i in range(1,n):
    t = int(input())
    k = bisect.bisect_left(L, t)
    if k == 0:
        L.appendleft(t)
    else:
        L[k-1] = t
print(len(L))

Solution (Python):

from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.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)
    a = [-i for i in a]
    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):
import bisect
from collections import deque

n = int(input())
A = []
dq_A = deque(A)
count = 0
for _ in range(n):
    a = int(input())
    if len(dq_A) == 0:
        dq_A.appendleft(a)
        count += 1
        continue
    i = bisect.bisect_left(dq_A, a)
    if i == 0:
        dq_A.appendleft(a)
        count += 1
    else:
        dq_A[i-1] = a

ans = count
print(ans)

Solution (Python):
from collections import deque
def lower_bound(al, key):
    def isOk(a):
        return a<key

    ng = len(al)
    ok = -1

    while abs(ok-ng)>1:
        mid = (ok+ng)//2

        if isOk(al[mid]):
            ok = mid
        else:
            ng = mid

    return ok

n = int(input())
al = [int(input()) for _ in range(n)]
c = deque()

for a in al:
    if len(c) == 0:
        c.append(a)
        continue

    idx = lower_bound(c,a)
    if idx==-1:
        c.appendleft(a)
    else:
        c[idx] = a

print(len(c))

Solution (Python):

n = int(input())
from collections import deque
import bisect
first = int(input())
a = [first]
a = deque(a) 

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

Solution (Python):


import bisect

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

Q = []
x = 0

for a in A:
    idx = bisect.bisect_right(Q, -a)

    if idx >= len(Q):
        x += 1
        Q.append(-a)
    else:
        Q[idx] = -a

print(x)

Solution (Python):
import bisect
from collections import deque
n = int(input())
l = deque([])
l.append(int(input()))
for i in range(n-1):
    a = int(input())
    if l[0] >= a:
        l.appendleft(a)
    else:
        l[bisect.bisect_left(l,a)-1] = a
print(len(l))

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:
    idx = bisect_left(dq, e)
    if idx == 0:
        dq.appendleft(e)
    else:
        dq[idx-1] = e

ans = len(dq)
print(ans)

Solution (Python):
from collections import deque
from bisect import bisect_left
n = int(input())
a = [int(input()) for _ in range(n)]
ans = deque([a[0]])
for a_i in a[1:]:
    if ans[0] < a_i:
        i = bisect_left(ans, a_i)
        ans[i-1] = a_i
    else:
        ans.appendleft(a_i)

print(len(ans))

Solution (Python):
from bisect import bisect_right
n = int(input())
ans = 1
data = [-int(input())]
for i in range(n-1):
    x = -int(input())
    j = bisect_right(data,x)
    if j == ans:
        data.append(x)
        ans += 1
    else:
        data[j] = x
print(ans)

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

import bisect
from collections import deque
q = deque()
q.append(a[0])

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

print(len(q))

Solution (Python):

import sys
read = sys.stdin.readline


def read_a_int():
    return int(read())


from bisect import bisect_left, bisect_right, insort_left
from array import array


class BinarySearchTree:
    def __init__(self, ls: list = []):
        '''
        C++でいうsetを実装する。二分探索木をガチで実装しようとすると大変なので、ここでは配列二分法を用いる。
        pythonの標準ライブラリがヨイショに抱っこしてくれるおかげで楽に実装できる。
        https://docs.python.org/ja/3/library/bisect.html


        ls ... 渡す初期配列
        '''
        self.bst = array('q', sorted(
            ls))  

    
    

    def __len__(self):
        return len(self.bst)

    def __getitem__(self, idx):
        return self.bst[idx]

    def size(self):
        return len(self.bst)

    def insert(self, x):
        
        
        insort_left(self.bst, x)

    def pop_left(self):
        x = self.bst[0]
        del self.bst[0]
        return x

    def pop_right(self):
        x = self.bst[-1]
        del self.bst[-1]
        return x

    def remove(self, x):
        '''
        xを取り除く。xがself.bstに存在することを保証してください。
        同一のものが存在した場合は左から消していく
        '''
        del self.bst[self.find(x)]

    def bisect_left(self, x):
        '''
        ソートされた順序を保ったまま x を self.bst に挿入できる点を探し当てます。
        lower_bound in C++
        '''
        return bisect_left(self.bst, x)

    def bisect_right(self, x):
        '''
        bisect_left() と似ていますが、 self.bst に含まれる x のうち、どのエントリーよりも後ろ(右)にくるような挿入点を返します。
        upper_bound in C++
        '''
        return bisect_right(self.bst, x)

    def find(self, x):
        '''
        xのidxを探索
        '''
        idx = bisect_left(self.bst, x)
        if idx != len(self.bst) and self.bst[idx] == x:
            return idx
        raise ValueError

    def insert_replace_left(self, x):
        '''
        xを挿入して、xの左の数字(次に小さい)を削除する。idxがはみ出す場合は挿入だけ
        '''
        idx_del = self.bisect_left(x) - 1
        if idx_del + 1 == 0:  
            self.insert(x)
        if idx_del < len(self.bst):
            self.insert(x)
            del self.bst[idx_del]

    def insert_replace_right(self, x):
        '''
        xを挿入して、xの右の数字(次に大きい)を削除する。idxがはみ出す場合は挿入だけ
        '''
        idx_del = self.bisect_right(x) + 1  
        if idx_del - 1 == len(self.bst):  
            self.insert(x)
        else:
            self.insert(x)
            del self.bst[idx_del]


N = read_a_int()
bst = BinarySearchTree([-1])
for n in range(N):
    a = read_a_int()
    
    if bst.bst[0] >= a:
        bst.insert(a)
    else:
        
        idx = bst.bisect_left(a) - 1
        bst.bst[idx] = a

print(len(bst))

Solution (Python):

import sys
read = sys.stdin.readline


def read_a_int():
    return int(read())


from bisect import bisect_left, bisect_right, insort_left
from collections import deque
from array import array


class BinarySearchTree:
    def __init__(self, ls: list = []):
        '''
        C++でいうsetを実装する。二分探索木をガチで実装しようとすると大変なので、ここでは配列二分法を用いる。
        pythonの標準ライブラリがヨイショに抱っこしてくれるおかげで楽に実装できる。
        https://docs.python.org/ja/3/library/bisect.html


        ls ... 渡す初期配列
        '''
        self.bst = array('l',sorted(ls))  

    def __len__(self):
        return len(self.bst)

    def __getitem__(self, idx):
        return self.bst[idx]

    def size(self):
        return len(self.bst)

    def insert(self, x):
        idx = self.bisect_left(x)
        self.bst.insert(idx, x)
        

    def pop_left(self):
        x = self.bst[0]
        del self.bst[0]
        return x

    def pop_right(self):
        x = self.bst[-1]
        del self.bst[-1]
        return x

    def remove(self, x):
        '''
        xを取り除く。xがself.bstに存在することを保証してください。
        同一のものが存在した場合は左から消していく
        '''
        del self.bst[self.find(x)]

    def bisect_left(self, x):
        '''
        ソートされた順序を保ったまま x を self.bst に挿入できる点を探し当てます。
        lower_bound in C++
        '''
        return bisect_left(self.bst, x)

    def bisect_right(self, x):
        '''
        bisect_left() と似ていますが、 self.bst に含まれる x のうち、どのエントリーよりも後ろ(右)にくるような挿入点を返します。
        upper_bound in C++
        '''
        return bisect_right(self.bst, x)

    def find(self, x):
        '''
        xのidxを探索
        '''
        idx = bisect_left(self.bst, x)
        if idx != len(self.bst) and self.bst[idx] == x:
            return idx
        raise ValueError

    def insert_replace_left(self, x):
        '''
        xを挿入して、xの左の数字(次に小さい)を削除する。idxがはみ出す場合は挿入だけ
        '''
        idx_del = self.bisect_left(x) - 1
        if idx_del + 1 == 0:  
            self.insert(x)
        if idx_del < len(self.bst):
            self.insert(x)
            del self.bst[idx_del]

    def insert_replace_right(self, x):
        '''
        xを挿入して、xの右の数字(次に大きい)を削除する。idxがはみ出す場合は挿入だけ
        '''
        idx_del = self.bisect_right(x) + 1  
        if idx_del - 1 == len(self.bst):  
            self.insert(x)
        else:
            self.insert(x)
            del self.bst[idx_del]


N = read_a_int()
bst = BinarySearchTree([-1])
for n in range(N):
    a = read_a_int()
    
    if bst.bst[0] >= a:
        bst.insert(a)
    else:
        
        idx = bst.bisect_left(a) - 1
        bst.bst[idx] = a

print(len(bst))

Solution (Python):
import bisect

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

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

Solution (Python):
def main():
    from bisect import bisect_right
    n=int(input())
    a=[int(input()) for _ in range(n)]

    color=[]
    for i in range(n-1,-1,-1):
        num=a[i]
        idx=bisect_right(color,num)
        if idx==len(color):
            color.append(num)
        else:
            color[idx]=num
    
    print(len(color))    
if __name__=='__main__':
    main()

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

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

N = int(input())
A = [int(input()) for _ in range(N)]
nums = deque()
for i in range(N):
    j = bisect_left(nums, A[i])
    if j == 0:
        nums.appendleft(A[i])
    else:
        nums[j-1] = A[i]
print(len(nums))

Solution (Python):
import bisect
import collections

N=int(input())

line=collections.deque()

for _ in range(N):
    A=int(input())
    index=bisect.bisect_left(line,A)
    if index==0:
        line.appendleft(A)
    else:
        line[index-1]=A
    
    
    

print(len(line))