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

for i in range(n-1):
  a=int(input())
  b=bisect.bisect_left(A,a,lo=0,hi=len(A))
  if b==0:
    A.appendleft(a)
  else:
    A[b-1]=a
print(len(A))

Solution (Python):
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod2 = 998244353
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

n = inp()
a = inpln(n)
q = deque([])

for i,j in enumerate(a):
  if i == 0:
    q.append(j)
    continue
  c = bisect.bisect_left(q,j)
  if c == 0:
    q.appendleft(j)
  else:
    q[c-1] = j
    
print(len(q))

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

n=int(input())
a=list(int(input()) for i in range(n))
b=deque()
b.append(-1)


for i in range(n):
    if a[i]>b[0]:
        x=bisect.bisect_right(b,a[i]-1)
        b[x-1]=a[i]
    else:
        b.appendleft(a[i])
print(len(b))

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


n = int(input())
color_box = deque([-1])

for _ in range(n):
    num = int(input())
    idx = bisect.bisect_left(color_box, num)
    if idx == 0:
        color_box.appendleft(num)
    else:
        color_box[idx-1] = num

print(len(color_box))

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

q=[]

def bisect_desc(a,x):
    r = len(a)
    if r == 0:
        return 0
    l = 0
    while l != r:
        f = (l+r)//2
        if a[f] >= x:
            l = f+1
        else:
            r = f
    return l

for sa in a:
    t = bisect_desc(q,sa)
    if t ==len(q):
        q.append(sa)
    else:
        q[t] = sa

print(len(q))

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

q=[]

def bisect_desc(a,x):
    r = len(a)
    if r == 0:
        return 0
    l = 0
    while l != r:
        f = (l+r)//2
        if a[f] >= x:
            l = f+1
        else:
            r = f
    return l

for sa in a:
    t = bisect_desc(q,sa)
    if t ==len(q):
        q.append(sa)
    else:
        q[t] = sa

print(len(q))

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

q=[]
def bisect_desc(a,x):
    r = len(a)
    if r == 0:
        return 0
    l = 0
    while l != r:
        f = (l+r)//2
        if a[f] >= x:
            l = f+1
        else:
            r = f
    return l

for sa in a:
    t = bisect_desc(q,sa)
    if t ==len(q):
        q.append(sa)
    else:
        q[t] = sa

print(len(q))

Solution (Python):

import bisect




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

INF = 10**10
dp = [INF] * (N+1)

answer = 0
for a in A:
  r = bisect.bisect_right(dp, a)
  if dp[r] > a:
    if dp[r] == INF:
      answer += 1
    dp[r] = a
print(answer)

Solution (Python):
from bisect import bisect_right as right




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

INF = 10**10
dp = [INF] * (N+1)

answer = 0
for a in A:
  r = right(dp, a)
  if dp[r] > a:
    if dp[r] == INF:
      answer += 1
    dp[r] = a
print(answer)

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

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

INF = 10**10
dp = [INF] * (N+1)

answer = 0
for a in A:
  r = right(dp, a)
  if dp[r] > a:
    if dp[r] == INF:
      answer += 1
    dp[r] = a
print(answer)

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


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

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


if __name__ == '__main__':
	solve()

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

Solution (Python):

import sys
from collections import deque
from bisect import bisect_left

def solve(N: int, A: "List[int]"):
    b = deque([A[0]])
    for a in A[1:]:
        if a <= b[0]:
            b.appendleft(a)
        else:
            idx = bisect_left(b, a)
            b[idx-1] = a
    print(len(b))
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    A = [int(next(tokens)) for _ in range(N)]  
    solve(N, A)

if __name__ == '__main__':
    main()

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
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)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n = I()
A = IR(n)
LIS = deque([A[0]])
for i in range(1, n):
    if A[i] <= LIS[0]:
        LIS.appendleft(A[i])
    else:
        LIS[bisect_left(LIS, A[i]) - 1] = A[i]


print(len(LIS))

Solution (Python):
import sys
import bisect

stdin = sys.stdin
 
ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split()))
rs = lambda: stdin.readline().rstrip()  

N = ri()
A = [10 ** 10 - ri() for _ in range(N)]
l = []
for a in A:
    i = bisect.bisect_right(l, a)
    if i == len(l):
        l.append(a)
    else:
        l[i] = a

print(len(l))

Solution (Python):
import sys
import bisect

stdin = sys.stdin
 
ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split()))
rs = lambda: stdin.readline().rstrip()  

N = ri()
INF = 10 ** 18
A = [10 ** 10 - ri() for _ in range(N)]
dp = [INF] * (N+1)
for a in A:
    i = bisect.bisect_right(dp, a)
    dp[i] = a

print(bisect.bisect_left(dp, INF))

Solution (Python):
from bisect import bisect_right

N = int(input())
S = [1]

for _ in range(N):
    a = int(input())
    a *= -1
    i = bisect_right(S, a)

    if i == len(S):
        S.append(a)
    else:
        S[i] = a

print(len(S))

Solution (Python):

import bisect

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

ans_list = [-1] * n
for i in range(n):
    tmp = bisect.bisect_left(ans_list, a[i])
    
    if tmp == 0:
        ans_list.insert(0, a[i])
    else:
        ans_list[tmp-1] = a[i]
    

ans = 0
for i in range(n):
    if ans_list[i] != -1:
        ans += 1
print(ans)

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

N = int(input())

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

dp = [float("inf")] * N



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

answer = bisect.bisect_left(dp, float("inf"))
print(answer)

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

N = int(input())

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

dp = [float("inf")] * N


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

answer = bisect.bisect_left(dp, float("inf"))
print(answer)

Solution (Python):
import bisect
import collections


def sequence_decomposing(N: int, A: list)->int:
    mins = collections.deque([A[0]])

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

    return len(mins)


if __name__ == "__main__":
    N = int(input())
    A = [int(input()) for _ in range(N)]
    ans = sequence_decomposing(N, A)
    print(ans)

Solution (Python):
import bisect
from collections import deque

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

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

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

print(len(LDS))

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()
from bisect import bisect
def resolve():
    n=int(input())
    A=[-int(input()) for _ in range(n)]
    Q=[]
    for a in A:
        i=bisect(Q,a)
        if(i==len(Q)): Q.append(a)
        else: Q[i]=a

    print(len(Q))
resolve()

Solution (Python):
from bisect import bisect_left
n=int(input())
x=[-1]*n
for _ in range(n):
    a=int(input())
    i=bisect_left(x,a)-1
    x[i]=a
print(n-x.count(-1))

Solution (Python):
from bisect import bisect as br
n=int(input())
x=[-1]*n
for _ in range(n):
    a=int(input())
    i=br(x,a-1)-1
    x[i]=a
print(n-x.count(-1))

Solution (Python):
import bisect
from collections import deque

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

L = deque()
L.append(A[0])
for i in range(1, N):
    if A[i] <= L[0]:
        L.appendleft(A[i])
    elif A[i] > L[-1]:
        L[-1] = A[i]
    else:
        idx = bisect.bisect_left(L, A[i])
        L[idx-1] = A[i]
        
print(len(L))

Solution (Python):
import bisect
n = int(input())
a = [int(input()) for i in range(n)]
c = [a[-1]]
for i in a[n-2::-1]:
  if c[-1] <= i:
    c.append(i)
  else:
    c[bisect.bisect_left(c,i+1)] = i
  
print(len(c))

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

Solution (Python):
import bisect
import collections

N=int(input())
A=[int(input()) for i in range(N)]
B=[0 for i in range(N)]
C=sorted(A)
count=0
lst=collections.deque([])
for i in range(N):
    if A[i]==C[-1]:
        C.pop()
        if lst:
            lst.pop()
        else:
            count+=1
        continue
    idx=bisect.bisect_left(lst,A[i])-1
    
    if idx<0:
        lst.appendleft(A[i])
        count+=1
    else:
        lst[idx]=A[i]

print(count)

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

L=[-1]*N
for i in A:
    n=bisect_left(L,i)
    L[n-1]=i

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

Solution (Python):
from bisect import bisect_right

N = int(input())
A = [int(input()) for _ in range(N)]
B = [A[-1]]
ans = 1
for a in reversed(A[:-1]):
    idx = bisect_right(B, a)
    if idx == ans:
        B.append(a)
        ans += 1
    else:
        B[idx] = a
print(ans)

Solution (Python):
import bisect
from collections import deque

n = int(input())
l = deque([int(input())])

for i in range(1, n):
  a = int(input())
  p = bisect.bisect_left(l,a)
  if p == 0:
    l.appendleft(a)
  else:
    l[p-1] = a

print(len(l))

Solution (Python):
import bisect
from collections import deque

n = int(input())
l = deque([int(input())])

for i in range(1, n):
  a = int(input())
  p = bisect.bisect_left(l,a)
  if p == 0:
    l.appendleft(a)
  else:
    l[p-1] = a

print(len(l))

Solution (Python):
import sys
input = sys.stdin.readline
n = int(input())
a = [int(input()) for _ in range(n)]
memo = []
ans = 0

def reverse_binary_serch(target, query):
    l = 0
    r = len(target) - 1
    while True:
        if r - l < 2:
            if target[l] < query:
                return l
            else:
                return r
        i = (l + r) // 2
        if target[i] >= query:
            l = i
        else:
            r = i

for ai in a:
    if not memo or memo[-1] >= ai:
        memo.append(ai)
    else:
        index = reverse_binary_serch(memo, ai)
        memo[index] = ai

print(len(memo))

Solution (Python):
import bisect
import sys
import collections
input = sys.stdin.readline
N = int(input())
A = [int(input()) for i in range(N)]
B = [A[0]]
B = collections.deque(B)
tmp = [0]*N
ans = 1
for i in range(1, N):
    id = bisect.bisect_left(B, A[i])
    if id == 0:
        B.appendleft(A[i])
    else:
        B[id-1] = A[i]
print(len(B))

Solution (Python):
import bisect
import sys
import collections
input = sys.stdin.readline
N = int(input())
A = [int(input()) for i in range(N)]
B = [A[0]]
B = collections.deque(B)
tmp = [0]*N
ans = 1
for i in range(1, N):
    id = bisect.bisect_left(B, A[i])
    if id == 0:
        B.appendleft(A[i])
    else:
        B[id-1] = A[i]
print(len(B))

Solution (Python):
import bisect
import sys

input = sys.stdin.readline

ri = lambda: int(input())
rs = lambda: input().rstrip()
ril = lambda: list(map(int, input().split()))
rsl = lambda: input().rstrip().split()
ris = lambda n: [ri() for _ in range(n)]
rss = lambda n: [rs() for _ in range(n)]
rils = lambda n: [ril() for _ in range(n)]
rsls = lambda n: [rsl() for _ in range(n)]

n = ri()
ls = ris(n)
ls = [-x for x in ls]

dp = [float('inf')] * n
for x in ls:
    dp[bisect.bisect_right(dp, x)] = x
print(bisect.bisect_left(dp, float('inf')))

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

print(len(LIS))

Solution (Python):
import bisect

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

B=[]
c=0
for a in A:
  p=bisect.bisect_right(B,a)
  if p==c:
    B.append(a)
    c += 1
  else:
    B[p]=a

print(len(B))

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


n = int(input())
A = [int(input()) for _ in range(n)]
A = A[::-1]
color = [10**10]

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

print(len(color))

Solution (Python):
import bisect


def main():
    N = int(input())
    A = [int(input()) for _ in range(N)][::-1]
    ans = [A[0], ]
    bright = bisect.bisect_right
    L = 1
    for i, a in enumerate(A):
        if i == 0:
            continue
        index = bright(ans, a)
        if index == L:
            ans.append(a)
            L += 1
        else:
            ans[index] = a
    print(L)


if __name__ == "__main__":
    main()

Solution (Python):
import sys
from bisect import bisect_right

input = sys.stdin.readline

def main():
    N = int(input())
    A = [int(input()) for _ in range(N)]
    n = [A.pop(-1)]
    A.reverse()
    
    for a in A:
        if n[-1] <= a: n.append(a)
        else: n[bisect_right(n, a)] = a
    
    print(len(n))

if __name__ == '__main__':
    main()

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

Solution (Python):
from bisect import bisect_right

def main():    
    N = int(input())
    A = [int(input()) for i in range(N)]
    n = [A.pop(-1)]
    A.reverse()
    
    for a in A:
        if n[-1] <= a: n.append(a)
        else: n[bisect_right(n, a)] = a
    
    print(len(n))

if __name__ == '__main__':
    main()

Solution (Python):
import bisect
n=int(input())
a=[int(input()) for i in range(n)]
l=[-1]*n
ans=0
for i in range(n):
  l[bisect.bisect_left(l,a[i])-1]=a[i]
print(n-l.count(-1))

Solution (Python):
from bisect import bisect_right
N = int(input())
A = []
for i in range(N):
    A.append(-int(input()))
INF = float('inf')
D = [INF] * N
for i in range(len(A)):
  
    D[bisect_right(D, A[i])] = A[i]

print(N - D.count(INF))

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

a=[-int(input()) for _ in range(n)]
x=[a[0]]
for i in a[1:]:
  y=bisect.bisect(x,i)
  if y==len(x):x.append(i)
  else:x[y]=i
print(len(x))

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

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

from collections import deque

import bisect
n = int(input())

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



d = deque()
d.appendleft(a[0])

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

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

from collections import deque

import bisect
n = int(input())

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



d = deque()
d.appendleft(a[0])

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

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):
import bisect

N = int(input())
A = [-1]*N

for _ in range(N):
    val = int(input())
    n = bisect.bisect_left(A, val)
    A[n-1] = val

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

Solution (Python):
import sys
from bisect import bisect_left
read = sys.stdin.read
readline = sys.stdin.readline


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

    a = [-1] * N

    for i in A:
        n = bisect_left(a, i)
        a[n - 1] = i

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


if __name__ == '__main__':
    main()

Solution (Python):
import sys
from bisect import bisect_left
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

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

a = [-1] * N

for i in A:
    n = bisect_left(a, i)
    a[n - 1] = i

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

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    from bisect import bisect
    n=int(input())
    A=[-int(input()) for _ in range(n)]
    B=[]
    for a in A:
        i=bisect(B,a)
        if(i==len(B)): B.append(a)
        else: B[i]=a
    print(len(B))
resolve()

Solution (Python):
import bisect

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

Q = [A[0]] + [0] * (n+1)
le = 1
for i in range(1, n):
    if Q[le-1] <= A[i]:
        Q[le] = A[i]
        le += 1
    else:
        ind = bisect.bisect_right(Q, A[i], 0, le)
        Q[ind] = A[i]
    

print(le)

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

Q = [-float("inf"), A[0]] + [float("inf")] * (n+1)
le = 2
for i in range(1, n):
    if Q[le-1] >= A[i]:
        Q[le] = A[i]
        le += 1
    else:
        l = 0
        r = le
        m = (l+r)//2
        while r-l > 1:
            if Q[m] >= A[i]:
                l = m
            else:
                r = m
            m = (l+r)//2
        Q[l+1] = A[i]
    

print(le-1)

Solution (Python):
import bisect

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


colors = []


for i,n in enumerate(list(reversed(A))):
    
    if i == 0:
        colors.append(n)
    else:
        
        
        idx = bisect.bisect_right(colors, n)
        
        if colors[-1] <= n:
            colors.append(n)
        else:
            colors[idx] = n

print(len(colors))

Solution (Python):
import bisect

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


colors = []


for i,n in enumerate(list(reversed(A))):
    
    if i == 0:
        colors.append(n)
    else:
        
        
        
        idx = bisect.bisect_right(colors, n)
        if idx == len(colors):
            colors.append(n)
        else:
            colors[idx] = n

print(len(colors))

Solution (Python):
import bisect
n = int(input())
l = [0 for i in range(n)]
for i in range(n):
    a1 = int(input())
    l[n-1-i] = a1
h = [l[0]]
ans = 1
for i in range(1,n):
    a = bisect.bisect_right(h,l[i])
    if ans == a:
        ans += 1
        h.append(l[i])
    else:
        h[a] = l[i]
print(ans)

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

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

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

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

Solution (Python):
import bisect
N = int(input())
A = [int(input())for i in range(N)]
m = [-A[0]]
ans = 1
for i in A[1:]:
    p = bisect.bisect_left(m,-i+1)
    if p == ans:
        ans += 1
        m.append(-i)
    else:
        m[p] = -i
print(ans)

Solution (Python):
import bisect
N = int(input())
A = [int(input()) for _ in range(N)]
first = [-1 for _ in range(N)]
for a in A:
    i = bisect.bisect_left(first,a)
    first[i-1] = a
ctr = N
for f in first:
    if f == -1:
        ctr -= 1
print(ctr)

Solution (Python):
from collections import deque
import bisect
import sys
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
ans = int(0)

N = I()
color = []
a = I()
maxcolor =deque()
maxcolor.append(a)
lena = 1
for i in range(N-1):
    minmaxcolor = maxcolor[0]
    a = I()
    if a<=minmaxcolor:
        maxcolor.appendleft(a)

        lena += 1
    else:
        acandi = bisect.bisect_left(maxcolor, a)
        maxcolor[acandi-1] = a
        """
        aupper = lena-1
        alower = int(0)
        acandi = aupper//2
        
        for _ in range(aupper+1):
            if maxcolor[acandi]>=a:
                alower = acandi
                acandi = (aupper+acandi+1)//2
            else:
                if aupper - alower <= 1:
                    maxcolor[acandi] = a
                    break
                else:
                    aupper = acandi
                    acandi = (acandi + alower) // 2
        """


ans = len(maxcolor)
print(ans)

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

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

dp=[float("inf")]*(n+1)
for b in a:
    idx=bisect.bisect_right(dp,b)
    dp[idx]=b

ans=bisect.bisect_left(dp,float("inf"))

print(ans)

Solution (Python):

n=int(input())
lists=[0]*n
for i in range(n):
    lists[i]=int(input())
import bisect
counter=0
lislist=[lists[-1]]
for i in range(2,n+1):
    a=lists[-i]
    index=bisect.bisect_right(lislist,a)
    if index<len(lislist):
        lislist[index]=a

    elif index==len(lislist):
        lislist.append(a)

print(len(lislist))

Solution (Python):

n=int(input())
lists=[0]*n
for i in range(n):
    lists[i]=int(input())
import bisect
counter=0
lislist=[lists[-1]]
for i in range(2,n+1):
    a=lists[-i]
    index=bisect.bisect_right(lislist,a)
    if index<len(lislist):
        lislist[index]=a

    elif index==len(lislist):
        lislist.append(a)

print(len(lislist))

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

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

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([-x for x in A],wider_sense=True)
print(answer)

Solution (Python):
import bisect

INF = 10000000000

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

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

dp = [INF] * n

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

Solution (Python):

def longest_subsequence(A: "Array[int]", equals: bool, increasing: bool) -> int:
    from bisect import bisect_left, bisect_right

    bs = bisect_right if equals else bisect_left
    compare = (lambda x, y: x >= y) if equals else (lambda x, y: x > y)
    if not increasing:
        A = A[::-1]
    
    dp = [A[0]]  
    for i in A[1:]:
        if compare(i, dp[-1]):
            dp.append(i)
        else:
            dp[bs(dp, i)] = i
    return len(dp)


def main():
    N, *A = map(int, open(0))
    ans = longest_subsequence(A, equals=1, increasing=0)
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):

def lis(A: "Array[int]") -> int:
    from bisect import bisect_right

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


def main():
    N, *A = map(int, open(0))
    ans = lis(A[::-1])  
    print(ans)


if __name__ == "__main__":
    main()

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

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


print(len(arr))

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

from bisect import bisect_right

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

def LIS(seq):
    
    N = len(seq)
    INF = 10**18
    dp = [INF] * (N+1)
    for x in seq:
        i = bisect_right(dp,x)
        dp[i] = x
    return bisect_right(dp,INF-1)

answer = LIS([-x for x in A])
print(answer)

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


colors = deque()
for n in l:
    
    ind = bisect.bisect_left(colors, n)
    if ind == 0:
        colors.appendleft(n)
    else:
        colors[ind-1] = n
print(len(colors))

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

print(len(h))

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

de = deque([])
de.append(A[0])
for a in A[1:]:
    ind = bl(de, a)
    if ind == 0:
        de.appendleft(a)
    else:
        de[ind-1] = a

print(len(de))

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

de = deque([])
de.append(A[0])
for a in A[1:]:
    ind = bl(de, a)
    if ind == 0:
        de.appendleft(a)
    else:
        de[ind-1] = a

print(len(de))

Solution (Python):

inf=float("inf")
from heapq import heappop,heappush 
n=int(input())
a=[int(input()) for _ in range(n)]
dp=[-1]*(n)
dp[0]=a[0]
for i in range(1,n):
    m=0
    M=n-1
    while M-m>1:
        if dp[(M+m)//2]<a[i]:
            M=(M+m)//2
        else:
            m=(M+m)//2
    if dp[m]>=a[i]:
        dp[M]=a[i]
    else:
        dp[m]=a[i]
count=0
for i in range(n):
    if dp[i]!=-1:
        count+=1
    else:
        break
print(count)

Solution (Python):
class SegTree:
    def __init__(self, init_val, n, ide_ele, seg_func):
        self.segfunc = seg_func
        self.num = 2**(n-1).bit_length()
        self.ide_ele = ide_ele
        self.seg=[self.ide_ele]*2*self.num
        for i in range(n):
            self.seg[i+self.num-1]=init_val[i]    
        for i in range(self.num-2,-1,-1) :
            self.seg[i]=self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 
        
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        while k+1:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1],self.seg[k*2+2])
        
    def query(self, p, q):
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res=self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res,self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res,self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res,self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res,self.seg[p]),self.seg[q])
        return res

n = int(input())
xs = [int(input()) for _ in range(n)]
d = {}
for i, x in enumerate(sorted(xs)):
    d[x] = i

segtree = SegTree([0]*n, n, 0, max)
r = 0
for x in xs:
    xi = d[x]
    y = segtree.query(xi, n)
    segtree.update(xi, y+1)
    r = max(r, y+1)
print(r)

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

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

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

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

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

q = deque([A[0]])

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

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

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

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

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