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 bisect import bisect
import sys
input = sys.stdin.readline
n = int(input())
A = [int(input()) for _ in range(n)]
dp = [1]
for a in A:
    a *= -1
    i = bisect(dp,a)   

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


print(len(dp))

Solution (Python):

from bisect import bisect
n = int(input())
A = [int(input()) for _ in range(n)]
dp = [1]
for a in A:
    a *= -1
    i = bisect(dp,a)   

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


print(len(dp))

Solution (Python):
from bisect import bisect_right as br
N = int(input())
inf = 10 ** 9 + 1
lis = [inf] * (N + 1)
res = 0
for _ in range(N):
  a = -int(input())
  ind = br(lis, a)
  if a <= lis[ind]:
    lis[ind] = a

for i in range(1, N + 1):
  if lis[i] == inf:
    break
  res = i
print(res + 1)

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

if __name__ == '__main__':
    main()

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

A = []
for _ in range(N):
    a = int(input())
    A.append(a)
    
nums = A[:]
colors = [float('inf')] * N

from bisect import bisect_left, bisect_right, insort_right
ans = 0
for n in nums:
    idx = bisect_right(colors, -n)
    colors[idx] = -n
    
    if idx > ans:
        ans = idx
    
            
print(ans+1)

Solution (Python):
from bisect import bisect_left, bisect_right
from collections import deque
import sys
input = sys.stdin.readline
n = int(input())
a = [int(input()) for _ in range(n)]

dq = deque([a[0]])
for i in range(1, n):
    idx = bisect_left(dq, a[i])
    if idx == 0:
        dq.appendleft(a[i])
    else:
        dq[idx-1] = a[i]

print(len(dq))

Solution (Python):



import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
a = [I() for _ in range(n)]

x = [float('inf') for _ in range(n)]
for i in range(n)[::-1]:
    r = bisect.bisect_right(x,a[i])
    x[r] = a[i]
cnt = x.count(float('inf'))
print(n-cnt)

Solution (Python):
from bisect import *

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

inf = float('inf')
ret = [inf] * N

ind = 0
for elem in A:
    i = bisect_right(ret, elem)
    ret[i] = elem
    if ind < i:
        ind = i

print(ind+1)

Solution (Python):
from bisect import bisect_left

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

min_stack = [a[-1]]

for i in range(2,n+1):
    if min_stack[-1] <= a[-i]:
        min_stack.append(a[-i])
    else:
        tmp = min_stack[bisect_left(min_stack, a[-i])]
        if tmp == a[-i]:
            min_stack[bisect_left(min_stack, a[-i]+1)] = a[-i]
        else:
            min_stack[bisect_left(min_stack, a[-i])] = a[-i]

print(len(min_stack))

Solution (Python):

import sys
import math
from collections import defaultdict


sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]


mod = 10**9 + 7


def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
    read_all = [tuple(map(int, input().split())) for _ in range(N)]
    return map(list,zip(*read_all))



from bisect import bisect_left

N = I()
A = [0]*N
for i in range(N):
    A[i] = I()

val = [-1]*N
for i in range(N):
    temp = bisect_left(val,A[i])
    val[temp-1] = A[i]

ans = 0
for i in range(N):
    if val[i]!=-1:
        ans += 1

print(ans)

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

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

colors = deque([10 ** 10])
for i in range(N):
    bi = bisect.bisect_left(colors, A[i])
    bir = bisect.bisect_right(colors, A[i])
    if bir == len(A):
        colors[len(A) - 1] = A[i]
    elif bi == 0:
        colors.appendleft(A[i])
    else:
        colors[bi - 1] = A[i]

print(len(colors) - 1)

Solution (Python):
from bisect import *


def p_e():
    N = int(input())
    
    ans = [-1] * N

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

    print(N - bisect(ans, -1))


if __name__ == '__main__':
    p_e()

Solution (Python):



from bisect import bisect_left
from collections import deque

def main():
  N = int(input())
  liA = list(map(int, [input() for _ in range(N)]))
  colors = deque([liA[0]])
  for a in liA[1:]:
    if a <= colors[0]:
      colors.appendleft(a)
    else:
      i = bisect_left(colors, a)
      colors[i-1] = a

  print(len(colors))
  pass

if __name__=='__main__':
  main()

Solution (Python):
from bisect import *
n = int(input())
a = [int(input()) for i in range(n)]

color = [-a[0]]
for i in range(1,n):
    if -a[i] >= color[-1]:
        color.append(-a[i])
    else:
        idx = bisect_right(color,-a[i])
        color[idx] = -a[i]

print(len(color))

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

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

li = [a[0]]
ans = 1

for i in range(1,n):
    if li[0] < a[i]:
        li[0] = a[i]
    elif li[-1] >= a[i]:
        li.append(a[i])
    else:
        p = 0
        q = len(li) - 1
        while p != q:
            c = (p + q) // 2
            if li[c] >= a[i]:
                p = c + 1
            else:
                q = c
        li[p] = a[i]

print(len(li))

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):
import bisect
n = int(input())
a = [int(input()) for _ in range(n)]

dp = [float('inf')]*n
for i in range(n):
    x = bisect.bisect_right(dp,-a[i])
    dp[x] = -a[i]
c = dp.count(float('inf'))
print(n-c)

Solution (Python):


import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7

n = int(input())
a = [int(input()) for _ in range(n)]
dp = [float('inf')]*n
for i in range(n):
    x = bisect.bisect_right(dp,-a[i])
    dp[x] = -a[i]
c = dp.count(float('inf'))
print(n-c)

Solution (Python):
from bisect import bisect_right
def solve(n, a):
    ans = 1
    L = [-a[0]]
    for i in range(1, n):
        x = -a[i]
        if x >= L[-1]:
            ans += 1
            L.append(x)
        else:
            L[bisect_right(L, x)] = x
    return ans

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

Solution (Python):
from bisect import bisect_right

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

b = []

ans = 1
b.append(a[n-1])

for i in range(n-2, -1, -1):
    if a[i] >= b[-1]:
        b.append(a[i])
    else:
        x = bisect_right(b,a[i])
        b[x] = a[i]
        x -= 1
        while x >= 0:
            if b[x] > b[x+1]:
                b[x],b[x+1] = b[x+1],b[x]
                x -= 1
            else:
                break
    

print(len(b))

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

num_col = 1
L = [-1*Alist[0]] 
for ai in Alist[1:]:
    
    ai =-1*ai
    if ai >= L[-1]:
        L.append(ai)
        num_col += 1
    else:
        L[bisect_right(L, ai)] = ai
print(num_col)

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


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

print(len(dp))

Solution (Python):

from bisect import bisect_right

N = int(input())

columns = []


for _ in range(N):
    current = -int(input())
    index = bisect_right(columns, current)
    if len(columns) <= index:
        columns.append(current)
    else:
        columns[index] = current

print(len(columns))

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

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

for i in range(1, N):

    index = bisect.bisect_right(now, -A[i])
    if index == len(now):
        now.append(-A[i])
    else:
        now[index] = -A[i]

print(len(now))

Solution (Python):
n=int(input())
a=[]
for i in range(n):
    a.append(-int(input()))
dp=[10**10 for i in range(n+1)]
import bisect
for i in a:
    idx=bisect.bisect_right(dp,i)
    dp[idx]=i

ans=bisect.bisect_left(dp,10**10)
print(ans)

Solution (Python):
import bisect

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

LIS = [a[-1]]
for i in range(n - 2, -1, -1):
    if a[i] >= LIS[-1]:
        LIS.append(a[i])
    else:
        LIS[bisect.bisect_right(LIS, a[i])] = a[i]

print(len(LIS))

Solution (Python):
import bisect
n = int(input())
a = []
for i in range(n):
    temp = int(input())
    a.append(temp)
a.reverse()
b = [a[0]]
counter = 1
for i in range(1,n):
    if a[i] >= b[-1]:
        counter += 1
        b.append(a[i])
    else:
        ind = bisect.bisect_right(b,a[i])
        b[ind] = a[i]
print(counter)

Solution (Python):
N = int(input())
L = []
from bisect import bisect_right
for _ in range(N):
    u = -int(input())
    index = bisect_right(L,u)

    if index == len(L):
        L.append(u)
    else:
        L[index ] = u
print(len(L))

Solution (Python):
from collections import deque
import bisect

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

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

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

print(len(ans))

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

N = int(input())
l = [-int(input())]

for i in range(N-1):
  ai = -int(input())

  if l[-1] <= ai:
    l.append(ai)
  else:
    b = bisect_right(l, ai)
    l[b] = ai
    
print(len(l))

Solution (Python):
import bisect
inf = 1000000009
n = int(input())
a = [int(input()) for i in range(n)]
b = [inf] * (n + 10)
for i in range(n):
    j = bisect.bisect_right(b, -a[i], 0, hi = len(b))
    b[j] = -a[i]
print(bisect.bisect_left(b, inf, 0, hi = len(b)))

Solution (Python):

from math import sqrt
from itertools import accumulate
from collections import Counter
from heapq import heappop, heappush
from bisect import bisect, bisect_left
import sys

input = sys.stdin.readline
def inpl(): return list(map(int, input().split()))


class BIT:
    def __init__(self, N):
        
        self.size = 2 ** (int.bit_length(N+1))
        self.node = [0]*(self.size + 1)
 
    def initialize(self, S):
        
        
        if len(S) < self.size + 1:
            S += [S[-1]] * (self.size+1 - len(S))
        for i in range(1, self.size+1):
            self.node[i] = S[i] - S[i - (i&-i)]
 
    def sum(self, i):
        res = 0
        while i:
            res += self.node[i]
            i -= (i & -(i))
        return res
 
    def add(self, i, x):
        if i == 0:
            return
        while i <= self.size:
            self.node[i] += x
            i += (i & -(i))
 
    def bisect_left(self, x):
        res = 0
        tmp = 0
        b = 2**(int.bit_length(self.size)-2)
        while b:
            if tmp + self.node[res+b] < x:
                res += b
                tmp += self.node[res]
            b //= 2
        return res + 1
 
    def bisect(self, x):
        res = 0
        tmp = 0
        b = 2**(int.bit_length(self.size)-2)
        while b:
            if tmp + self.node[res+b] <= x:
                res += b
                tmp += self.node[res]
            b //= 2
        return res + 1


class DammySet:

    def __init__(self, counter, INF=2**32, counter_is_unique_and_sorted=True, filled=1):
        if not counter_is_unique_and_sorted:
            if type(counter) != Counter:
                counter = Counter(counter)

            self.bit = BIT(len(counter.keys())+3)
            self.key = sorted([-INF, -INF] + sorted(counter.keys()) + [INF])
            self.val = [counter[k] for k in self.key]
            S = list(accumulate(self.val))
            self.bit.initialize(S)

        else:
            self.bit = BIT(len(counter) + 3)
            self.key = [-INF] * (len(counter) + 3)
            self.key[-1] = INF
            self.val = [0] * (len(counter) + 3)
            for i in range(2, len(counter)+2):
                self.key[i] = counter[i-2]
                self.val[i] = filled

            if filled:
                S = [0] * (len(counter) + 3)
                for i in range(2, len(counter)+2):
                    S[i] = i-1
                S[-1] = len(counter)
                self.bit.initialize(S)

    def add(self, val):
        ix = bisect_left(self.key, val)
        assert self.key[ix] == val
        self.bit.add(ix, 1)

    def delete(self, val):
        ix = bisect_left(self.key, val)
        assert self.key[ix] == val
        self.bit.add(ix, -1)


    def update(self, vals):
        for k, v in Counter(vals).items():
            ix = bisect_left(self.key, k)
            if self.key[ix] != k:
                raise KeyError
            self.bit.add(ix, v)


    def remove(self, vals):
        for k, v in Counter(vals).items():
            ix = bisect_left(self.key, k)
            if self.key[ix] != k:
                raise KeyError
            
            
            
            assert self.bit.sum(ix) - self.bit.sum(ix-1) > 0

            self.bit.add(ix, -v)

    def find_lt(self, v):
        
        rk = bisect_left(self.key, v) - 1
        rs = self.bit.sum(rk)
        return self.bit.bisect_left(rs)


    def pop_vals(self, l, r):
        assert l <= r

        rix = bisect(self.key, r) - 1
        lix = bisect_left(self.key, l) - 1
        
        rv = self.bit.sum(rix)
        lv = self.bit.sum(lix)
        delta = rv - lv
        tv = lv+1
        tix = lix*1

        vix = 0
        rmvix = 0
        vals = [0]*delta
        rmvk = [0]*delta
        rmvv = [0]*delta
        while delta:
            OK = self.bit.bisect_left(tv)
            c = self.bit.sum(OK)
            d = c - tv + 1
            for _ in range(d):
                vals[vix] = self.key[OK]
                vix += 1
            rmvk[rmvix] = OK
            rmvv[rmvix] = d
            rmvix += 1
            tv += d
            tix = OK
            delta -= d

        for i in range(rmvix):
            self.bit.add(rmvk[i], -rmvv[i])
        return vals

N = int(input())
A = [int(input()) for _ in range(N)]
C = sorted(set(A))
dset = DammySet(C, filled=0)
L =  len(dset.bit.node) - 1

for i in range(N):
    ix = dset.find_lt(A[i])
    if ix > 1:
        dset.bit.add(ix, -1)
    dset.add(A[i])

print(dset.bit.sum(L))

Solution (Python):

from math import sqrt
from itertools import accumulate
from collections import Counter
from heapq import heappop, heappush
from bisect import bisect, bisect_left
import sys

input = sys.stdin.readline
def inpl(): return list(map(int, input().split()))


class BIT:
    def __init__(self, N):
        
        self.size = 2 ** (int.bit_length(N+1))
        self.node = [0]*(self.size + 1)
 
    def initialize(self, S):
        
        
        if len(S) < self.size + 1:
            S += [S[-1]] * (self.size+1 - len(S))
        for i in range(1, self.size+1):
            self.node[i] = S[i] - S[i - (i&-i)]
 
    def sum(self, i):
        res = 0
        while i:
            res += self.node[i]
            i -= (i & -(i))
        return res
 
    def add(self, i, x):
        if i == 0:
            return
        while i <= self.size:
            self.node[i] += x
            i += (i & -(i))
 
    def bisect_left(self, x):
        res = 0
        tmp = 0
        b = 2**(int.bit_length(self.size)-2)
        while b:
            if tmp + self.node[res+b] < x:
                res += b
                tmp += self.node[res]
            b //= 2
        return res + 1
 
    def bisect(self, x):
        res = 0
        tmp = 0
        b = 2**(int.bit_length(self.size)-2)
        while b:
            if tmp + self.node[res+b] <= x:
                res += b
                tmp += self.node[res]
            b //= 2
        return res + 1


class DammySet:

    def __init__(self, counter, INF=2**32, counter_is_unique_and_sorted=True, filled=1):
        if not counter_is_unique_and_sorted:
            if type(counter) != Counter:
                counter = Counter(counter)

            self.bit = BIT(len(counter.keys())+3)
            self.key = sorted([-INF, -INF] + sorted(counter.keys()) + [INF])
            self.val = [counter[k] for k in self.key]
            S = list(accumulate(self.val))
            self.bit.initialize(S)

        else:
            self.bit = BIT(len(counter) + 3)
            self.key = [-INF] * (len(counter) + 3)
            self.key[-1] = INF
            self.val = [0] * (len(counter) + 3)
            for i in range(2, len(counter)+2):
                self.key[i] = counter[i-2]
                self.val[i] = filled

            if filled:
                S = [0] * (len(counter) + 3)
                for i in range(2, len(counter)+2):
                    S[i] = i-1
                S[-1] = len(counter)
                self.bit.initialize(S)

    def add(self, val):
        ix = bisect_left(self.key, val)
        assert self.key[ix] == val
        self.bit.add(ix, 1)

    def delete(self, val):
        ix = bisect_left(self.key, val)
        assert self.key[ix] == val
        self.bit.add(ix, -1)


    def update(self, vals):
        for k, v in Counter(vals).items():
            ix = bisect_left(self.key, k)
            if self.key[ix] != k:
                raise KeyError
            self.bit.add(ix, v)


    def remove(self, vals):
        for k, v in Counter(vals).items():
            ix = bisect_left(self.key, k)
            if self.key[ix] != k:
                raise KeyError
            
            
            
            assert self.bit.sum(ix) - self.bit.sum(ix-1) > 0

            self.bit.add(ix, -v)

    def find_lt(self, v):
        
        rk = bisect_left(self.key, v) - 1
        rs = self.bit.sum(rk)
        return self.bit.bisect_left(rs)

    def find_gt(self, v):
        lk = bisect(self.key, v) - 1  
        ls = self.bit.sum(lk)
        return self.bit.bisect(ls) 


    def find_ge(self, v):
        lk = bisect_left(self.key, v) - 1 
        ls = self.bit.sum(lk)
        return self.bit.bisect(ls) 


    def pop_vals(self, l, r):
        assert l <= r

        rix = bisect(self.key, r) - 1
        lix = bisect_left(self.key, l) - 1
        
        rv = self.bit.sum(rix)
        lv = self.bit.sum(lix)
        delta = rv - lv
        tv = lv+1
        tix = lix*1

        vix = 0
        rmvix = 0
        vals = [0]*delta
        rmvk = [0]*delta
        rmvv = [0]*delta
        while delta:
            OK = self.bit.bisect_left(tv)
            c = self.bit.sum(OK)
            d = c - tv + 1
            for _ in range(d):
                vals[vix] = self.key[OK]
                vix += 1
            rmvk[rmvix] = OK
            rmvv[rmvix] = d
            rmvix += 1
            tv += d
            tix = OK
            delta -= d

        for i in range(rmvix):
            self.bit.add(rmvk[i], -rmvv[i])
        return vals

N = int(input())
A = [int(input()) for _ in range(N)]
C = sorted(set(A))
dset = DammySet(C, filled=0)
L =  len(dset.bit.node) - 1

for i in range(N):
    ix = dset.find_lt(A[i])
    if ix > 1:
        dset.bit.add(ix, -1)
    dset.add(A[i])
    


print(dset.bit.sum(L))

Solution (Python):
N = int(input())
a = int(input())
l = [a]
d = {a: 1}
ans = 1
for _ in range(1, N):
    a = int(input())
    if a in d:
        d[a] += 1
        if l[-1] == a:
            ans += 1
        else:
            i = l.index(a) + 1
            v = l[i]
            if d[v] == 1:
                del d[v]
                l.remove(v)
            else:
                d[v] -= 1
    else:
        v = l[0]
        if v < a:
            if d[v] == 1:
                del d[v]
                l[0] = a
            else:
                d[v] -= 1
                l.insert(0, a)
        elif l[-1] > a:
            l.append(a)
            ans += 1
        else:
            left, right = 0, len(l) - 1
            while left + 1 != right:
                i = (left + right) // 2
                x = l[i]
                if x > a:
                    left = i
                else:
                    right = i
            v = l[right]
            if d[v] == 1:
                del d[v]
                l[right] = a
            else:
                d[v] -= 1
                l.insert(right, a)
        d[a] = 1
print(ans)

Solution (Python):
import sys
import bisect
input = sys.stdin.readline
n = int(input().strip())
q = [-int(input().strip())]
qapp = q.append
bis_r = bisect.bisect_right
for i in range(n-1):
  a = -int(input().strip())
  if q[-1] <= a:
    qapp(a)
  else:
    b = bis_r(q,a)
    q[b] = a
print(len(q))

Solution (Python):
import sys
import bisect
from collections import deque
input = sys.stdin.readline
n = int(input().strip())
q = deque()
qappL = q.appendleft
for i in range(n):
  a = int(input().strip())
  b = bisect.bisect_left(q,a)
  if b == 0:
    qappL(a)
  else:
    q[b-1] = a
print(len(q))

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

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

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


dp = []
for a in A:
    i = bisect_right(dp, a)
    if i >= len(dp):
        dp.append(a)
    else:
        dp[i] = a

print(len(dp))

Solution (Python):
import bisect

N = int(input())

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

colors = []

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

    if target == len(colors):
        colors.append(A[i])
    else:
        colors[target] = A[i]

print(len(colors))

Solution (Python):

def desc_bin(a, x, lo=0, hi=None):
    """Insert item x in list a, and keep it reverse-sorted assuming a
    is reverse-sorted.

    If x is already in a, insert it to the right of the rightmost x.

    Optional args lo (default 0) and hi (default len(a)) bound the
    slice of a to be searched.
    """
    if lo < 0:
        raise ValueError('lo must be non-negative')
    if hi is None:
        hi = len(a)
    while lo < hi:
        mid = (lo+hi)//2
        if x > a[mid]: hi = mid
        else: lo = mid+1
    return lo
N=int(input())
ans=[]
for _ in range(N):
    num=int(input())
    
    index=desc_bin(ans,num)
    if index==len(ans):
        ans.append(num)
    else:
        ans[index]=num
    
print(len(ans))

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

a = list(map(lambda x: -x, a))
m = len(a)

lis = [float('inf')]*m

for x in a:
  lis[bisect.bisect_right(lis, x)] = x

print(len([x for x in lis if not (x == float('inf'))]))

Solution (Python):
import sys
import bisect
import collections


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


def main():
    n = int(input())
    la = [int(input()) for _ in range(n)]
    result = collections.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))


main()

Solution (Python):
import bisect

N = int(input())
A = [int(input()) for _ in range(N)]
M = 10**9
color = []

for i in A:
    tmp = M-i
    if len(color) == 0:
        color.append(tmp)
    elif tmp >= color[-1]:
        color.append(tmp)
    else:
        color[bisect.bisect_right(color, tmp)] = tmp

print(len(color))

Solution (Python):
import bisect

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

ans = 1
X = [-A[0]]
for i in range(1,N):
    if -X[ans-1] >= A[i]:
        X.append(-A[i])
        ans += 1
    else:
        pos = bisect.bisect_right(X,-A[i])
        X[pos] = -A[i]

print(ans)

Solution (Python):


import sys
from bisect import bisect_right

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N=INT()
A=[INT() for i in range(N)]

def LIS(A: list):
    L = [A[0]]
    for a in A[1:]:
        if a >= L[-1]:
            
            L.append(a)
        else:
            
            
            L[bisect_right(L, a)] = a
    return len(L)


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

Solution (Python):


import sys
from collections import deque
from bisect import bisect_left

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

def LDS(A: list):
    L = deque([A[0]])
    for a in A[1:]:
        if a <= L[0]:
            
            L.appendleft(a)
        else:
            
            
            L[bisect_left(L, a)-1] = a
    return len(L)

N=INT()
A=[INT() for i in range(N)]

print(LDS(A))

Solution (Python):
import bisect
import collections

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

C = collections.deque()

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

print(len(C))

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

def LIS(L):
    from bisect import bisect
    seq = []
    for a in L:
        pos = bisect(seq, a)
        if len(seq) <= pos:
            seq.append(a)
        else:
            seq[pos] = a
    return len(seq)

n = int(input())
a = []
for _ in range(n):
    a.append(int(input()))
print(LIS(a[::-1]))

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

Solution (Python):
from bisect import *
N = int(input())
A = [-int(input()) for i in range(N)]
dp = [float("inf")]*N
for a in A :
    ind = bisect_right(dp, a)
    dp[ind] = a
print(bisect_left(dp, float("inf")))

Solution (Python):
"""
賢過ぎる解法.汎用性が高そう.
"""
from bisect import bisect

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

data = [inputs[0]]
for i in range(1, N):
    index = bisect(data, inputs[i])
    if index == len(data):
        data.append(inputs[i])
    else:
        data[index] = inputs[i]

print(len(data))

Solution (Python):
import bisect
from collections import deque

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

colors = deque([])
colors.append(a_list[0])
for i in range(1, N):
    a = a_list[i]
    idx = bisect.bisect_left(colors, a)
    if idx == 0:
        colors.appendleft(a)
    else:
        colors[idx-1] = a

print(len(colors))

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

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

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

print(len(q))

Solution (Python):
import bisect
from collections import deque
def solve():
  n = int(input())
  a = [int(input()) for _ in range(n)]
  t = 1
  ans = deque([])
  for i,w in enumerate(a):
   if i == 0:
      ans.append(w)
   else:
    
    place = bisect.bisect_left(ans,w)
    if place == 0:
      ans.appendleft(w)
      t += 1
    else:
      ans[place-1] = w

  print(len(ans))
  
  
solve()

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

t = [a[-1]]
 
for i in reversed(a[:-1]):
    
    idx = bisect.bisect_left(t, i+1)
    
    if idx == len(t):
        t.append(i)
    
    else:
        t[idx] = i
    
 
print(len(t))

Solution (Python):
import bisect

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

t = [a[-1]]

for i in reversed(a[:-1]):
    
    idx = bisect.bisect_left(t, i+1)
    
    if idx == len(t):
        t.append(i)
    
    else:
        t[idx] = i
    

print(len(t))

Solution (Python):
import bisect

N = int(input())

a = - int(input())

a_array = [a]

for i in range(N-1):
    a = - int(input())
    index = bisect.bisect_right(a_array,a)
    if index == len(a_array):
        a_array.append(a)
    else:
        a_array[index] = a
    
print(len(a_array))

Solution (Python):
def bisect_right_descending(a, x, lo=0, hi=None):
    if lo < 0:
        raise ValueError('lo must be non-negative')
    if hi is None:
        hi = len(a)
    while lo < hi:
        mid = (lo+hi)//2
        if x > a[mid]: hi = mid
        else: lo = mid+1
    return lo


n = int(input())

b = []

for i in range(n):
    a = int(input())
    c = bisect_right_descending(b,a)
    if c==len(b):
        b.append(a)
    else:
        b[c]=a

print(len(b))