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):
"""
A = a1,a2,a3,a4,...
同じ色のとき、i<jならai<aj

が成り立つときの最小の色の数
"""

from bisect import bisect_right

prev = 10**9+7
cnt = 0
As = [-prev]
n = int(input())
for _ in range(n):
    a = int(input())
    update = bisect_right(As,-a)
    if update-1 == cnt:
        As.append(-a)
        cnt += 1
    else:
        As[update] = -a 
    prev = a

print(cnt)

Solution (Python):
"""
A = a1,a2,a3,a4,...
同じ色のとき、i<jならai<aj

が成り立つときの最小の色の数

2 1 4 5 3

8
5 
4 
3 
2 
1 
3 
2 
1

5
4
3
2 3
1 2
1



"""

from bisect import bisect_right

prev = 10**9+7
cnt = 0
As = [-prev]
n = int(input())
for _ in range(n):
    a = int(input())
    update = bisect_right(As,-a)
    if update-1 == cnt:
        As.append(-a)
        cnt += 1
    else:
        As[update] = -a 
    prev = a

print(cnt)

Solution (Python):
import bisect
from collections import deque

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

b = deque([])
for a in A:
  if len(b) == 0:
    b.append(a)
  else:
    if a <= b[0]:
      b.appendleft(a)
    else:
      b[bisect.bisect_left(b, a) - 1] = a
print(len(b))

Solution (Python):
import bisect
import collections

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

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

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


print(len(ans))

Solution (Python):
from collections import deque
from bisect import bisect_left
inf = float('inf')


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

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

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

ans = len(color)
print(ans)

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

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

b = deque([])

for ai in a:
    if len(b) == 0:
        b.append(ai)
    else:
        if ai <= b[0]:
            b.appendleft(ai)
        else:
            idx = bisect_left(b, ai)
            b[idx-1] = ai

print(len(b))

Solution (Python):
from collections import deque
import bisect

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


b = deque([])

for ai in a:
    if len(b) == 0:
        b.append(ai)
    else:
        if ai <= b[0]:
            b.appendleft(ai)
        else:
            index = bisect.bisect_left(b, ai)
            b[index-1] = ai

print(len(b))

Solution (Python):
import collections, bisect

def resolve():

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

    d = collections.deque()

    for i in range(n):
        change_index = bisect.bisect_left(d, ai[i]) - 1
        if change_index == -1:
            d.appendleft(ai[i])
        else:
            d[change_index] = ai[i]

    print(len(d))
    
resolve()

Solution (Python):
from bisect import bisect_left

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

color = [-1]*N

for i in range(N):
    pos = bisect_left(color, A[i])
    color[pos-1] = A[i]

ans = len([c for c in color if c != -1])
print(ans)

Solution (Python):
from bisect import bisect_left

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

color = [-1]*N

ans = 0
l = N

for i in range(N):
    pos = bisect_left(color, A[i])
    if pos == l:
        ans += 1
    color[pos-1] = A[i]

ans = len([c for c in color if c != -1])
print(ans)

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

def bisect_right_reverse(a, x, lo=0, hi=None):
    """Return the index where to insert item x in list a, assuming a is sorted.
    The return value i is such that all e in a[:i] have e <= x, and all e in
    a[i:] have e > x.  So if x already appears in the list, a.insert(x) will
    insert just after the rightmost x already there.
    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 hi


c = []
for i in range(N):
    n = int(input())
    index = bisect_right_reverse(c,n)
    
    if index == len(c):
        c.append(n)
    else:
        c[index] = n
    

print(len(c))

Solution (Python):
import sys,collections as cl,bisect as bs,math,heapq as hq
sys.setrecursionlimit(100000)
Max = sys.maxsize
def l(): 
	return list(map(int,input().split()))
def m(): 
	return map(int,input().split())
def onem(): 
	return int(input())
def s(x): 
	a = []
	aa = x[0]
	su = 1
	for i in range(len(x)-1):
		if aa == x[i+1]:
			a.append([aa,su])
			aa = x[i+1]
			su = 1
		else:
			su += 1
	a.append([aa,su])
	return a
def jo(x): 
	return " ".join(map(str,x))
def max2(x): 
	return max(map(max,x))

def LIS(L):
  L = L[::-1]
  LIS=[]
  for i in L:
    pos = bs.bisect_right(LIS,i) 
    if len(LIS) <= pos:
      LIS.append(i)
    else:
      LIS[pos]=i
  return len(LIS)

n = onem()

a = []
c = 0
for i in range(n):
	a.append(onem())


print(LIS(a))

Solution (Python):
import sys
input=sys.stdin.readline
from bisect import bisect_right
n=int(input())
A=[-int(input()) for _ in range(n)]
LIS=[]
for a in A:
    idx=bisect_right(LIS,a)
    if idx==len(LIS):
        LIS.append(a)
    else:
        LIS[idx]=a
print(len(LIS))

Solution (Python):
import sys
input=sys.stdin.readline
from bisect import bisect_right
n=int(input())
A=[-int(input())-1 for _ in range(n)]
M=[0]*n
for a in A:
    idx=bisect_right(M,a)
    M[idx]=a
print(sum(m!=0 for m in M))

Solution (Python):
import bisect
from collections import deque
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]
print(len(d))

Solution (Python):
import bisect as bs
import collections

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

col = collections.deque()
min_ = 10000000000

for a in alist:
    if a <= min_:
        col.appendleft(a)
    else:
        index = bs.bisect_left(col, a) - 1
        col[index] = a
    min_ = col[0]

print(len(col))

Solution (Python):
import sys
import numpy as np

pin = np.fromstring(sys.stdin.buffer.read(), dtype=np.int32, sep='\n')
N = pin[0]
a = pin[1:]
b = -1 -a
c = np.zeros(N, dtype=np.int32)
for d in b:
    i = np.searchsorted(c, d, side='right')
    c[i] = d

print((c < 0).sum())

Solution (Python):
import sys
s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in ss]
ss2nnn = lambda ss: [s2nn(s) for s in ss]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [sys.stdin.readline().rstrip() for _ in range(n)]
ii2sss = lambda n: [list(sys.stdin.readline().rstrip()) for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))

from bisect import bisect_left, bisect_right  
from collections import deque  

def main_ok():
    N = i2n()
    A = ii2nn(N)
    B = [1]
    for a in A:
        t = bisect_right(B, -a)
        if t < len(B):
            B[t] = -a
        else:
            B.append(-a)
    print(len(B))

def main():
    N = i2n()
    A = ii2nn(N)
    B = deque()
    B.appendleft(-1)
    for a in A:
        t = bisect_left(B, a)
        if t > 0:
            B[t-1] = a
        else:
            B.appendleft(a)
    print(len(B))

main()

Solution (Python):
import bisect
def LIS():
    L[0] = A[0]
    length = 1
    for i in range(1, N):
        if L[length-1] < A[i]:
            L[length] = A[i]
            length += 1
        else:
            j = bisect.bisect_left(L, A[i])
            L[min(length-1, j)] = A[i]
    return length

def LISDesc():
    L[0] = A[-1]
    length = 1
    for i in range(N-2, -1, -1):
        if L[length-1] <= A[i]:
            L[length] = A[i]
            length += 1
        else:
            j = bisect.bisect_right(L, A[i])
            L[min(length-1, j)] = A[i]
    return length

INFTY = 10**13
N = int(input())
A = [int(input()) for i in range(N)]
L = [INFTY for i in range(N)]
ans = LISDesc()
print(ans)

Solution (Python):

import bisect

n=int(input())
arr=[int(input()) for _ in range(n)][::-1]
LIS=[arr[0]]
for i in range(1,n):
  if arr[i]>=LIS[-1]:
    LIS.append(arr[i])
  else:
    LIS[bisect.bisect_right(LIS,arr[i])]=arr[i]
print(len(LIS))

Solution (Python):
from bisect import bisect as bl

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

def lds(X: list):
    L = [-X[0]]
    for x in X[1:]:
        if L[-1] <= -x:
            L.append(-x)
        else:
            L[bl(L, -x)] = -x
    return len(L)

print(lds(A))

Solution (Python):
import bisect

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

A.reverse()
ans = [A[0]]

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

print(len(ans))

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

Solution (Python):
from itertools import*
from math import*
from collections import*
from heapq import*
from bisect import bisect_left,bisect_right,bisect
from copy import deepcopy
inf = float("inf")
mod = 10**9+7
from functools import reduce
import sys
sys.setrecursionlimit(10**7)

N = int(input())
LIS = []
for i in range(N):
    a =- int(input())
    idx = bisect(LIS,a)
    if idx == len(LIS):
        LIS.append(a)
    else:
        LIS[idx]=a
print(len(LIS))

Solution (Python):
from bisect import bisect_left

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

c = [0] * n
end = n

for ai in a:
    ci = bisect_left(c, ai, end, n)
    c[ci - 1] = ai
    if ci <= end:
        end -= 1
print(n - end)

Solution (Python):
import bisect

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

for i in range(N):
    hoge = bisect.bisect(result,S[i])
    if hoge == len(result):
        result.append(S[i])
    else:
        result[hoge] = S[i]
print(len(result))

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

r = [-1]*N

mind = float("inf")
for n in range(N):
    ind = bisect.bisect_left(r, a[n])
    r[ind-1] = a[n]
    mind = min(mind, ind)


print(N-mind+1)

Solution (Python):
def binary_search(A,func):
    l = 0
    r = len(A)-1
    if func(0,A):return -1
    if not func(r,A):return r
    while l+1<r:
        i = (l+r)//2
        if func(i,A):
            r = i
        else:
            l = i
    return l

N = int(input())
A = [int(input()) for _ in [0]*N]
B = [A[0]]
ans = 1
for a in A[1:]:
    r = binary_search(B,lambda i,b:b[i]<a)+1
    if r < ans:B[r] = a
    else:
        B.append(a)
        ans+=1
print(ans)

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

color = deque([a.pop(0)])
color_count =0 
for ai in a: 
    index = bisect.bisect_left(color, ai)
    if index > 0:
        color[index -1] = ai
    else:
        color.appendleft(ai)
print(len(color))

Solution (Python):

from bisect import bisect_right, bisect_left
N = int(input())
a_list = [int(input()) for _ in range(N)]

color_list = [1]
for a in a_list:
    a *= -1
    index = bisect_right(color_list, a)
    if index < len(color_list):
        color_list[index] = a
    else:
        color_list.append(a)

print(len(color_list))

Solution (Python):
n = int(input())
dat = []
for i in range(n):
    dat.append(int(input()))
res = []
res.append(0 - dat[0])

import bisect

for i in range(1, n):
    
    a = bisect.bisect_right(res, 0 - dat[i])
    

    if a == len(res):
        res.append( (0 - dat[i]) )
    else:
        res[a] = (0 - dat[i])

print(len(res))

Solution (Python):
a=int(input())
b=[int(input()) for i in range(a)]
LIS = [b[0]]
for i in range(1,len(b)):
  if b[i] <= LIS[-1]:
    LIS.append(b[i])
  else:
    lo=0
    hi=len(LIS)
    while lo < hi:
      mid=(lo+hi)//2
      if b[i]>LIS[mid]:
        hi =mid
      else:
        lo=mid+1  
    LIS[lo] = b[i]
print(len(LIS))

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

Solution (Python):
from bisect import bisect


def main():
    N = int(input())
    A = [-int(input()) for _ in range(N)]
    L = [A[0]]
    for a in A[1:]:
        if a >= L[-1]:
            L.append(a)
        else:
            L[bisect(L, a)] = a
    print(len(L))


if __name__ == "__main__":
    main()

Solution (Python):
import bisect
n=int(input())
A=[]
for i in range(n):
  A.append(int(input()))
Ans=[A[-1]]
for i in reversed(range(n-1)):
  a=A[i]
  if a>=Ans[-1]:
    Ans.append(a)
  else:

    Ans[bisect.bisect_right(Ans,a)]=a

print(len(Ans))

Solution (Python):
import bisect
N=int(input())
X=[-1]*N
for _ in X:a=int(input());X[bisect.bisect_right(X,a-1)-1]=a
print(N-X.count(-1))

Solution (Python):
from bisect import bisect_right as f
N=int(input())
X=[-1]*N
for _ in X:a=int(input());X[f(X,a-1)-1]=a
print(N-X.count(-1))

Solution (Python):



import bisect as bi


def solve():
    N = int(input())
    A = []
    heads = []
    for _ in range(N):
        A.append(int(input()))
    a = A.pop()
    bi.insort(heads, a)
    while A:
        a = A.pop()
        if a < heads[-1]:
            j = bi.bisect(heads, a)
            del heads[j]
        bi.insort(heads, a)
    return len(heads)
  

def main():
    print(solve())


if __name__ == "__main__":
    main()

Solution (Python):
from bisect import bisect_right
N=int(input())
X=[-1]*N
for _ in X:a=int(input());X[bisect_right(X,a-1)-1]=a
print(N-X.count(-1))

Solution (Python):

import bisect
from collections import deque

N = int(input())


c = deque()
c.appendleft(int(input()))


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

print(len(c))

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

import collections
n = int(input())
dat = []
for i in range(n):
    dat.append(int(input()))
res = collections.deque([])

res.append(dat[0])
import bisect

for i in range(1, n):
    a = bisect_right(res, dat[i])
    

    if a == len(res):
        res.append(dat[i])
    else:
        res[a] = dat[i]
print(len(res))

Solution (Python):
from bisect import bisect_right as br
INF = 10 ** 10
n = int(input())
alst = [int(input()) for _ in range(n)][::-1]
dp = [INF] * (n + 1)
dp[0] = -1
ans = 0
for a in alst:
  ind = br(dp, a)
  dp[ind] = a
  ans = max(ans, ind)
print(ans)

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
import bisect

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

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


seq = A[::-1]
LIS = [seq[0]]
for i in range(1, len(seq)):
	if seq[i] >= LIS[-1]:
		LIS.append(seq[i])
	else:
		LIS[bisect.bisect(LIS, seq[i])] = seq[i]

print(len(LIS))

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

Solution (Python):
import bisect
n=int(input())
a=[int(input()) for i in range(n)]
inf=10**9+1
tmp=[inf]*n
ans=0
for i in range(n-1,-1,-1):
  j= bisect.bisect_right(tmp,a[i])
  tmp[j]=a[i]
for i in range(n):
  if tmp[i]!=inf:
    ans+=1
print(ans)

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

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

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

fastinput = sys.stdin.readline
N = int(fastinput())
A = [int(fastinput()) for j in range(N)]
surface = deque([A[0]])
surfMax = A[0]
surfMin = A[0]
color = 1
for n,a in enumerate(A):
    if n==0:continue

    if color == 1:
        c = surface[0]
        if a>c:
            surface[0] = a
            surfMax = a
            surfMin = a
        if a==c:
            surface.appendleft(a)
            color += 1
        if a<c:
            surface.appendleft(a)
            color += 1
            surfMin = a

    else:    
        if a<=surfMin:
            color += 1
            surface.appendleft(a)
            surfMin = a
        elif a>surfMax:
            surface[color-1] = a
            surfMax = a
        else:
            pos = bisect.bisect_left(surface,a) -1 
            surface[pos] = a
            if pos==0:
                surfMin = a
            if pos == color-1:
                surfMax = a
print(color)

Solution (Python):
"""
演算子は要素とセットでモノイドを形成するようなものでなければならない。
すなわち、結合律が成り立ち単位元が存在する必要がある。

equalityはsetを高速化するために使う。めんどい場合はNoneにしてもOK
"""
class SegmentTree:

    @classmethod
    def all_identity(cls, operator, equality, identity, size):
        return cls(operator, equality, identity, [identity]*(2 << (size-1).bit_length()))

    @classmethod
    def from_initial_data(cls, operator, equality, identity, data):
        size = 1 << (len(data)-1).bit_length()
        temp = [identity]*(2*size)
        temp[size:size+len(data)] = data
        data = temp

        for i in reversed(range(size)):
            data[i] = operator(data[2*i],data[2*i+1])
        return cls(operator, equality, identity, data)

    
    def __init__(self, operator, equality, identity, data):
        if equality is None:
            equality = lambda a,b: False
        self.op = operator
        self.eq = equality
        self.id = identity
        self.data = data
        self.size = len(data)//2

    def _interval(self, a, b):
        a += self.size
        b += self.size
        ra = self.id
        rb = self.id

        data = self.data
        op = self.op
        while a < b:
            if a & 1:
                ra = op(ra,data[a])
                a += 1
            if b & 1:
                b -= 1
                rb = op(data[b],rb)
            a >>= 1
            b >>= 1
        return op(ra,rb)

    def __getitem__(self, i):
        if isinstance(i, slice):
            return self._interval(
                                    0 if i.start is None else i.start,
                                    self.size if i.stop is None else i.stop)
        elif isinstance(i, int):
            return self.data[i+self.size]

    def __setitem__(self, i, v):
        i += self.size
        data = self.data
        op = self.op
        eq = self.eq
        while i and not eq(data[i],v):
            data[i] = v
            v = op(data[i^1],v) if i & 1 else op(v,data[i^1])
            i >>= 1

    def __iter__(self):
        return self.data[self.size:]

from operator import eq

N = int(input())

B = sorted((v,-i) for i,v in enumerate(int(input()) for _ in range(N)))
B = [-i for v,i in B]
i_j = {j:i for i,j in enumerate(B)}

st = SegmentTree.from_initial_data(min, equality=eq, identity=N, data=B)

visit_cnt = 0
cnt = 0
while visit_cnt < N:
    j = 0
    while True:
        i = st[j:]
        if i == N:
            break
        j = i_j[i]
        visit_cnt += 1
        st[j] = N
    cnt += 1

print(cnt)

Solution (Python):
def seek(value):
    right = len(color_list) - 1
    left = 0
    while(True):
        mid = (right + left) // 2
        if(value > color_list[mid]):
            right = mid
        else:
            left = mid
        if(right - left <= 1):
            return right

N = int(input())    
color_list =  [int(input())]
for i in range(N-1):
    new_value = int(input())
    if(new_value > color_list[0]):
        color_list[0] = new_value
    elif(new_value <= color_list[-1]):
        color_list.append(new_value)
    else:
        new_index = seek(new_value)
        color_list[new_index] = new_value
print(len(color_list))

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

N=int(input())
A=[-int(input()) for _ in range(N)]
l=[A[0]]
for x in A[1::]:
    tmp=bisect.bisect(l,x)
    if tmp==len(l):l.append(x)
    else: l[tmp]=x
print(len(l))

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

Solution (Python):
import bisect

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

b = []
for i in range(n):
    k = bisect.bisect(b,-a[i])
    if k == len(b):
        b.append(-a[i])
    else:
        b[k] = -a[i]

print(len(b))

Solution (Python):
from bisect import bisect_right

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

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

print(len(L))

Solution (Python):
from bisect import bisect as bisect
def LIS(l):
    seq = []
    for a in l:
        i = bisect(seq,a)
        if len(seq)==i:
            seq.append(a)
        else:
            seq[i]=a
    return len(seq)

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

Solution (Python):


import math
import sys
import bisect


n =int(input())


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


c = [-999]*n

for i in range(0,n):



    p = bisect.bisect_left(c, a[i])
    c[p-1]=a[i]



print(len(c) - bisect.bisect_left(c, -1))

Solution (Python):


import math
import sys
import bisect


n =int(input())


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


c = [-999]*n

for i in range(0,n):



    p = bisect.bisect_left(c, a[i])
    c[p-1]=a[i]



print(len(c) - bisect.bisect_left(c, -1))

Solution (Python):
from heapq import heappush, heappop
from collections import deque
import sys

sys.setrecursionlimit(10**6)
def MI():
    return map(int,input().split())
def I():
    return int(input())
def LI():
    return [int(i) for i in input().split()]

def bisect(ls,x):
    l,r=0,len(ls)
    while r-l>1:
        mid=(l+r)//2
        if ls[mid]>=x: 
            r=mid
        else:
            l=mid
    
    return l

n=I()
a=deque()
q=[[] for _ in range(n)]
m=0 
for i in range(n):
    a+=[I()]


q=deque()
q.append(a.popleft())


while a:
    c=a.popleft()
    if c<=q[0]:
        q.appendleft(c)
        
    else:
        i=bisect(q,c)
        q[i]=c
        


ans=len(q)
print(ans)

Solution (Python):
import bisect
n=int(input())
A=[]
for i in range(n):
  A.append(int(input()))
Ans=[A[-1]]
for i in reversed(range(n-1)):
  a=A[i]
  if a>=Ans[-1]:
    Ans.append(a)
  else:

    Ans[bisect.bisect_right(Ans,a)]=a

print(len(Ans))

Solution (Python):
from bisect import bisect
N, *A = map(int, open(0).read().split())

INF = 10 ** 9 + 7
dp = [INF] * (N + 1)
for i in range(N):
    dp[bisect(dp, -A[i])] = -A[i]

print(sum(dp[i] < INF for i in range(N)))

Solution (Python):

import sys
from bisect import bisect


def solve(N: int, A: "List[int]"):

    A.reverse()
    res = [A[0]]
    for i in A[1:]:
        pos = bisect(res,i)
        if len(res) <= pos:
            res.append(i)
        else:      
            res[pos] = i

    print(len(res))
    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):
import bisect
 
 
def main():
    n = input()
    aa = []
    xx = [-input()]
    for _ in xrange(n - 1):
        aa.append(-input())
    for a in aa:
        if a >= xx[-1]:
            xx.append(a)
        else:
            i = bisect.bisect_right(xx, a)
            if i == len(xx):
                i -= 1
            xx[i] = a
    print len(xx)
 
 
if __name__ == '__main__':
    main()

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

color = 1
A[0] = int(input())


def search(A, color, a):
        left = 0
        right = color - 1
        signal = 0
        while left < right:
                mid = (left + right) // 2
                if A[mid] == a - 1:
                        return mid
                        signal = 1
                elif a <= A[mid]:
                        left = mid + 1
                else:
                        right = mid
        if signal == 0:
                return left


for i in range(N - 1):
        
        a = int(input())
        num = search(A, color, a)
        if num == color - 1 and a <= A[num]:
                A[color] = a
                color += 1
        else:
                A[num] = a

print(color)

Solution (Python):
import bisect
from collections import deque

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

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

print(len(ans))

Solution (Python):
import bisect

if __name__ == '__main__':
    n = int(input())
    a = [int(input()) for _ in range(n)]
    colors = [a[-1]]
    ans = 1
    for x in reversed(a[:-1]):
        i = bisect.bisect_left(colors, x + 1)
        if i == ans:
            ans += 1
            colors.append(x)
        else:
            colors[i] = x
    print(ans)

Solution (Python):
import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def _I(): return int(sys.stdin.readline())
def _F(): return float(sys.stdin.readline())
def _pf(s): return print(s, flush=True)

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

"""
何個色を使えば塗れるか
最も小さい数字からはじめれば？
最も左からはじめれば？
"""

def bisect(arr, val, cmp):
    l = -1
    r = len(arr)
    while r - l > 1:
        e = (l + r) >> 1
        if cmp(arr[e], val): l = e
        else: r = e
    return r

res = [] 
for a in A:
    
    if len(res) == 0:
        res.append(a)
    else:
        if a <= res[-1]:
            
            res.append(a)
        else:
            
            p = bisect(res, a, lambda x, y: x > y)
            if res[p] == a:
                p = bisect(res, a-1, lambda x, y: x > y)
                res[p] = a
            else:
                res[p] = a

print(len(res))

Solution (Python):
import bisect

N = int(input())
A = []

a = int(input())

val = [-a]
length = 1

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

    index = bisect.bisect_right(val, a)
    if index >= length :
        val.append(a)
        length += 1
    else :
        val[index] = a

print(length)

Solution (Python):

"""
Created on Sat Jul 20 20:53:54 2019

@author: ctiuser
"""

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

ans = [A[0]]

for i in range(1,N):
    l,r = 0, len(ans)-1
    p = (r-l)//2 + 1
    if A[i] <= ans[r]:
        ans.append(A[i])
    elif A[i] > ans[l]:
        ans[l] = A[i]
    else:
        tmp = r
        while r - l > 1:
            if A[i] > ans[p]:
                tmp = p
                r = p
                p = (r-l)//2 + l
            else:
                l = p
                p = (r-l)//2 + l
        ans[tmp] = A[i]

print(len(ans))

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


class BIT:
    def __init__(self, n):
        self.n = n
        self.data = [0] * (n + 1)
    def ope(self, x, y):
        return x + y
    def update(self, i, v):
        while i <= self.n:
            self.data[i] = self.ope(self.data[i], v)
            i += i & -i
    def query(self, i):
        ret = 0
        while 0 < i:
            ret = self.ope(self.data[i], ret)
            i &= i - 1
        return ret
    def lower(self, w):
        if w <= 0:
            return 0
        x = 0
        k = 2**(self.n.bit_length())
        while k:
            if x + k <= self.n and  self.data[x+k] < w:
                w -= self.data[x+k]
                x += k
            k >>= 1
        return x + 1



n = int(input())
a = [int(input()) for i in range(n)]
b = sorted(list(set(a)))
d = {}
for i, j in enumerate(b):
    d[j] = i
a = [d[i] for i in a]
k = len(d)

B = BIT(k)
ans = 0
for i in a:
    i = i+1
    q = B.query(i)
    if q == 0:
        B.update(i, 1)
        ans += 1
    else:
        v = B.lower(q)
        if v != i:
            B.update(v, -1)
            B.update(i, 1)
        else:
            w = B.query(i-1)
            if w == 0:
                B.update(i, 1)
                ans += 1
            else:
                v = B.lower(w)
                B.update(v, -1)
                B.update(i, 1)
print(ans)

Solution (Python):
import bisect
from collections import deque

N = int(input())


c = deque()
c.appendleft(int(input()))


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

print(len(c))