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


def solve():
    N = int(input())
    A = [int(input()) for _ in range(N)]
    color_list = [A[-1]]
    for a in reversed(A[:-1]):
        
        c = bisect.bisect_left(color_list, a + 1)
        if c == len(color_list):
            color_list.append(a)
        else:
            color_list[c] = a
    print(len(color_list))


if __name__ == '__main__':
    solve()

Solution (Python):
from bisect import bisect
n = int(input())
a = [int(input()) for _ in range(n)]
update_list=[11 for _ in range(n+1)]
for old_element in range(n):
    update_position=bisect(update_list,-a[old_element])
    update_list[update_position]=-a[old_element]

ans=0
while update_list[ans] <= 0:
	ans += 1
print(ans)

Solution (Python):
import bisect
from collections import deque

N = int(input())

tops = deque() 

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

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

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

Solution (Python):
import bisect

words = lambda t : list(map(t, input().split()))
n = int(input())
a = []
for i in range(n):
    a.append(-1 * int(input()))

b = []
b.append(a[0])

for i in range(1,n):
    x = a[i]
    x_ind = bisect.bisect_right(b,x)
    
    if x_ind >= len(b):
        b.append(x)
    else:
        b[x_ind] = x

print(len(b))

Solution (Python):
from bisect import bisect
n = int(input())
a = [int(input()) for _ in range(n)]
dp = [1 for _ in range(n+2)]
for i in range(n):
	b = bisect(dp, -a[i])
	dp[b] = -a[i]
ans = 1
while dp[ans] <= 0:
	ans += 1
print(ans)

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

n = int(input())
a = tuple(int(input()) for _ in range(n))

d = deque()

for ai in a:
    p = bisect_left(d, ai)  
    if p == 0:
        d.appendleft(ai)
    else:
        d[p - 1] = ai
ans = len(d)
print(ans)

Solution (Python):
import bisect

n = int(input())
num_list = []
for i in range(n):
    num_list.append(int(input()) * -1) 

dp = [1] * n 

for i in num_list:
    indx = bisect.bisect_right(dp, i)
    dp[indx] = min(dp[indx], i)

ans = sum(x < 1 for x in dp)

print(ans)

Solution (Python):
def e_sequence_decomposing(N, A):
    
    
    
    import bisect

    
    
    lnds = []  

    for a in A[::-1]:
        idx = bisect.bisect_right(lnds, a)
        if idx == len(lnds):
            lnds.append(a)
        else:
            lnds[idx] = a
    return len(lnds)

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

Solution (Python):
n=int(input())
a_list=[int(input()) for i in range(n)]
a_list.reverse()
INF=10**10
dp=[INF]*n
import bisect
for i in range(n):
    a=a_list[i]
    x=bisect.bisect_right(dp,a)
    dp[x]=a
ans=0
for i in range(n):
    if dp[i]!=INF:
        ans=i+1
print(ans)

Solution (Python):
import sys
input=sys.stdin.readline
n=int(input())
a_list=[int(input()) for i in range(n)]
a_list.reverse()
INF=10**10
dp=[INF]*n
import bisect
for i in range(n):
    a=a_list[i]
    x=bisect.bisect_right(dp,a)
    dp[x]=a
ans=0
for i in range(n):
    if dp[i]!=INF:
        ans=i+1
print(ans)

Solution (Python):
from bisect import bisect_right
N = int(input())
A = list(int(input()) for _ in range(N))
INF = 10 ** 9 + 1

dp = [INF]
for a in A:
    if -a >= dp[-1]:
        dp.append(-a)
    else:
        j = bisect_right(dp, -a)
        dp[j] = -a

print(len(dp))

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

input = sys.stdin.readline

def f(n):
    r = deque()
    for _ in range(n):
        a = int(input())
        i = bisect_left(r, a)
        if i:
            r[i - 1] = a
        else:
            r.appendleft(a)
    print(len(r))

n = int(input())
f(n)

Solution (Python):

from collections import defaultdict,deque
from heapq import heappush, heappop
import sys, math, bisect, random, itertools
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')


def A():
    n = II()
    print(n*n*3)
    return


def B():
    n, d = LI()
    print((n-1)//(2*d+1)+1)
    return


def C():
    n = II()
    a = IR(n)
    b = a[::1]
    b.sort()
    for i in range(n):
        if a[i] == b[-1]:
            print(b[-2])
        else:
            print(b[-1])
    return


def D():
    n = II()
    a = [0] + LI()
    for i in range(n // 2, 0, -1):
        x = sum(a[i::i])
        if x % 2 != a[i]:
            a[i] ^= 1
    ans = []
    x = 0
    for i in range(1, n + 1):
        if a[i]:
            ans.append(str(i))
            x += 1
    print(x)
    if x == 0:
        return
    print(" ".join(ans))
    return


def E():
    n = II()
    a = IR(n)
    dp = deque([a[0]])
    ans = 1
    for i in a[1:]:
        x = bisect_right(dp, i)
        y = bisect_left(dp, i)
        if y == 0:
            ans += 1
            dp.appendleft(i)
        else:
            if x == y:
                dp[y - 1] = i
            else:
                if y >= ans:
                    ans += 1
                    dp.append(i)
                else:
                    dp[y - 1] = i
    print(ans)
    return


def F():
    return


if __name__ == '__main__':
    E()

Solution (Python):


import sys

def DBsearch(L,x,narrow):
    n= len(L)
    if n==0: return 0
    if narrow and x in L: return L.index(x)
    last = L[-1]
    if x<last: return n
    if not narrow and x==last: return n
    
    idx= -1
    i= 0
    j= n-1
    while j>=i:
        if i==j:
            if x>L[i]: idx= i
            break
        
        mid= i + (j-i)//2
        if x<L[mid]:
            i= mid+1
        elif x==L[mid]:
            if narrow:
                idx= mid
                j  = mid - 1
            else:
                i = mid + 1
        else:
            idx= mid
            j= mid-1
    
    return idx

def lds(L,narrow):
    seq= []
    for x in L:
        if len(seq)==0 or x<seq[-1]:
            seq.append(x)
        elif x==seq[-1]:
            if narrow:
                seq[DBsearch(seq,x,narrow)]= x
            else:
                seq.append(x)
        else:
            seq[DBsearch(seq,x,narrow)]= x
    
    return len(seq)

n= int(sys.stdin.readline())
ai= [ int(sys.stdin.readline()) for _ in range(n) ]
print( lds( ai,False ) )

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

N=input()
A=[ int(sys.stdin.readline().strip())  for _ in range(N) ]

LIS=[]
for i,x in enumerate(A[::-1]):
	if i==0:
		LIS.append(x)
	elif LIS[-1]<=x:
		LIS.append(x)
	else:
		p=bisect_right(LIS,x)
		LIS[p]=x

print len(LIS)

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

N=input()
seq=[ int(sys.stdin.readline().strip())*-1  for _ in range(N) ]

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

print(len(LIS))

Solution (Python):
from bisect import *

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

r = [10**10] * N
index = -1
for i in range(N):
    j = bisect_right(r, -A[i])
    r[j] = -A[i]
    if j > index:
        index = j
print(index + 1)

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

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

l = deque()

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

print(len(l))

Solution (Python):
import bisect

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

Solution (Python):
import bisect

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

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

N=input()
A=[ int(sys.stdin.readline().strip())  for _ in range(N) ]

q=deque()

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

print len(q)

Solution (Python):

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

sys.setrecursionlimit(1000000)
mod = 1000000007


def A():
    n = I()
    print(3*n**2)
    return


def B():
    n,d = LI()
    f = [1]*(n+2*d+2)
    ans = 0
    for i in range(n):
        if f[i]:
            for j in range(i,i+2*d+1):
                f[j] = 0
            ans += 1
    print(ans)
    return


def C():
    n = I()
    a = IR(n)
    mi = max(a)
    if a.count(mi) > 1:
        for i in range(n):
            print(mi)
    else:
        b = [a[i] for i in range(n)]
        b.sort()
        b = b[::-1]
        for i in range(n):
            if mi != a[i]:
                print(mi)
            else:
                print(b[1])

    return


def D():
    n = I()
    a = LI()
    b = [0]*(n+1)
    for i in range(1,n+1)[::-1]:
        j = 2*i
        k = 0
        while j <= n:
            k ^= b[j]
            j += i
        if a[i-1]^k:
            b[i] = 1
    ans = []
    for i in range(n+1):
        if b[i]:
            ans.append(i)
    print(len(ans))
    if ans:
        print(*ans)
    return


def E():
    n = I()
    a = IR(n)
    mi = [float("inf")]*(n+1)
    ans = 0
    for i in range(n):
        mi[bisect.bisect_right(mi,-a[i])] = -a[i]
    for i in range(n+1):
        if mi[i] == float("inf"):
            break
    print(i)
    return


def F():
    n = I()

    return


if __name__ == "__main__":
    E()

Solution (Python):
from bisect import *

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

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

for i in range(N) :
    ind = bisect_right(dp, A[i])
    dp[ind] = A[i]

ans = bisect_left(dp,float("inf"))
print(ans)

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

def main():
    input = sys.stdin.readline
    N = int(input())
    q = deque()
    for _ in range(N):
        a = int(input())
        pos = bisect_left(q, a)
        if pos == 0:
            q.appendleft(a)
        else:
            q[pos-1] = a

    return len(q)


if __name__ == '__main__':
    print(main())

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

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

print(len(A))

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

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

Solution (Python):
import bisect
N = int(input())
arr = [int(input()) for i in range(N)]
dp = [-1 for _ in range(N)]
for i in arr:
    dp[bisect.bisect_left(dp, i) - 1] = i
print(sum([i >= 0 for i in dp]))

Solution (Python):
import bisect

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

print(sum([i >= 0 for i in dp]))

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

dp = [-A[0]]
def solve():
    import bisect
    for i in range(1, N):
        a = bisect.bisect_left(dp, -A[i]+0.1) 
        
        if a == len(dp):
            dp.append(-A[i])
        else:
            dp[a] = -A[i]
        
    return len(dp)


print (solve())

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

def main():
    input = sys.stdin.readline
    N = int(input())
    a = int(input())
    q = deque()
    q.append(a)
    ans = 1
    for _ in range(N-1):
        n = int(input())
        if n <= q[0]:
            q.appendleft(n)
            ans += 1
            continue

        if n > q[-1]:
            q[-1] = n
            continue

        pos = bisect_left(q, n)
        q[pos-1] = n
        min_ = q[0]

    return ans


if __name__ == '__main__':
    print(main())

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

n = int(input())

ide_ele = -1


num =2**((n-1).bit_length())
seg=[ide_ele]*(2*num)

def init(init_val):
    
    for i in range(n):
        seg[i+num-1]=init_val[i]    
    
    for i in range(num-2,-1,-1) :
        seg[i]=max(seg[2*i+1],seg[2*i+2]) 
    
def update(k,x):
    k += num-1
    seg[k] = x
    while k+1:
        k = (k-1)//2
        seg[k] = max(seg[k*2+1],seg[k*2+2])
    
def query(p,q):
    if q<=p:
        return ide_ele
    p += num-1
    q += num-2
    res=ide_ele
    while q-p>1:
        if p&1 == 0:
            res = max(res,seg[p])
        if q&1 == 1:
            res = max(res,seg[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = max(res,seg[p])
    else:
        res = max(max(res,seg[p]),seg[q])
    return res
    
def main():
    used = defaultdict(int)
    a = [int(input()) for i in range(n)]
    b = sorted(a)
    for i in range(n):
        a[i] = bisect.bisect_left(b,a[i])
    
    tank = [a[0]]
    used[a[0]] = 1
    update(a[0],a[0])
    
    for i in range(1,n):
        while True:
            if used[tank[0]] > 0:
                break
            else:
                heapq.heappop(tank)
        
        if tank[0] < a[i]:
            ma = query(0,a[i])
            
            used[ma] -= 1
            heapq.heappush(tank,a[i])
            used[a[i]] += 1
            if used[ma] == 0:
                update(ma,-1)
        else:
            heapq.heappush(tank,a[i])
            used[a[i]] += 1
        update(a[i],a[i])

    res = 0
    for e in tank:
        if used[e] > 0:
            res += 1
            used[e] -= 1
    print(res)

if __name__ == '__main__':
    main()

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


def main():
    N = int(stdin.readline().rstrip())
    As = [int(stdin.readline().rstrip()) for x in range(N)]
    dq = deque([])
    for A in As:
        idx = bisect.bisect_left(dq, A)
        if idx == 0:
            dq.appendleft(A)
        else:
            dq[idx - 1] = A
    print(len(dq))


if __name__ == "__main__":
    main()

Solution (Python):
from bisect import bisect
N, *A = map(int, open(0).read().split())
D = [1]*(N+1)
D[0] = -10**10

for a in A:
    idx = bisect(D, -a)
    D[idx] = min(D[idx], -a)
print(bisect(D, 0)-1)

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

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

maxims = [A[0]]
ans = 1
for a in A[1:]:
    if maxims[-1] > a:
        idx = bisect.bisect(maxims,a)
        maxims[idx] = a
    else:
        maxims.append(a)
        ans += 1
    
print(ans)

Solution (Python):
import sys
from bisect import *

input=sys.stdin.readline

def f(n):
    mi=-1
    r = [inf]*n
    for _ in range(n):
        a = -int(input())
        i = bisect_right(r, a)
        r[i]=a
        if i>mi:
            mi=i
    print(mi+1)

n = int(input())
inf=10**10
f(n)

Solution (Python):
N, *A = map(int, open(0).read().split())
P = [-e for e in set(A)]
P.sort()
P.append(1)
MP = {e: i for i, e in enumerate(P)}
N += 1

data = [0]*(N+1)
def get(k):
    r = 0
    while k:
        r += data[k]
        k -= k & -k
    return r
def add(k, x):
    while k <= N:
        data[k] += x
        k += k & -k
N0 = 2**(N-1).bit_length()
def lower_bound(x):
    w = i = 0
    k = N0
    while k:
        if i+k <= N and w + data[i+k] <= x:
            w += data[i+k]
            i += k
        k >>= 1
    return i+1

for a in A:
    j = MP[-a]
    i = lower_bound(get(j+1))
    if i != N+2:
        add(i, -1)
    add(j+1, 1)
print(get(N))

Solution (Python):
N, *A = map(int, open(0).read().split())
P = [-e for e in set(A)]
P.sort()
P.append(1)
MP = {e: i for i, e in enumerate(P)}
N += 1

data = [0]*(N+1)
def get(k):
    r = 0
    while k:
        r += data[k]
        k -= k & -k
    return r
def add(k, x):
    while k <= N:
        data[k] += x
        k += k & -k
N0 = 2**(N-1).bit_length()
def lower_bound(x):
    w = i = 0
    k = N0
    while k:
        if i+k <= N and w + data[i+k] <= x:
            w += data[i+k]
            i += k
        k >>= 1
    return i+1

for a in A:
    j = MP[-a]
    i = lower_bound(get(j+1))
    if i != N+2:
        add(i, -1)
    add(j+1, 1)
print(get(N))

Solution (Python):


import bisect
def lis(seq):
    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]
    return(len(LIS))

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

b = a[::-1]
print(lis(b))

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

import bisect
from collections import deque

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

Solution (Python):
import bisect

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

Solution (Python):
import bisect

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

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

for i in range(n):
    if i == 0:
        answer.append(-a[i])
    elif -answer[-1] >= a[i]:
        answer.append(-a[i])
    else:
        a_index = bisect.bisect_right(answer, -a[i])
        answer[a_index] = -a[i]

print(len(answer))

Solution (Python):
from bisect import bisect_left

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


dp = [-1 for _ in range(N)]
for a in A:
    dp[bisect_left(dp, a) - 1] = a
ans = sum(x >= 0 for x in dp)

print(ans)

Solution (Python):
import bisect

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

def LIS(A):
    """
    returns Longest Increasing Subsequence of list A.
    """
    B = [A[0]]
    for i in range(N-1):
        if A[i+1] >= B[-1]:
            B.append(A[i+1])
        else:
            index = bisect.bisect_left(B, A[i+1])
            B[index] = A[i+1]
    return B

def LDS(A):
    """
    returns Longest Decreasing Subsequence of list A.
    """
    A = A[::-1]
    B = [A[0]]
    for i in range(N-1):
        if A[i+1] >= B[-1]:
            B.append(A[i+1])
        else:
            index = bisect.bisect_right(B, A[i+1])
            B[index] = A[i+1]
    return B[::-1]


print(len(LDS(A)))

Solution (Python):
import sys, math, itertools, bisect, copy, re
from collections import Counter, deque, defaultdict






INF = float('inf')
MOD = 10 ** 9 + 7
EPS = 10 ** -7
sys.setrecursionlimit(1000000)








import heapq

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

B = []

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


print(len(B))

pass

Solution (Python):
def bi(l,x):
    ok = len(l)
    ng = -1
    while ok-ng > 1:
        mid = (ng+ok)//2
        if l[mid] < x:
            ok = mid
        else:
            ng = mid
    return ok

n = int(input())
a = [int(input()) for _ in range(n)]
t = [-1]
m = 1
for x in a:
    c = bi(t,x) 
    if c == m:
        t.append(x)
        m += 1
    else:
        t[c] = x
print(m)

Solution (Python):
import bisect

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

B = [A[N - 1]]
for i in reversed(range(0, N - 1)):
  if A[i] >= B[-1]:
    B.append(A[i])
  else:
    index = bisect.bisect_right(B, A[i])
    B[index] = A[i]
print(len(B))

Solution (Python):
import bisect
a=[-int(input()) for _ in [0]*int(input())]
dp=[]
for x in a:
    i = bisect.bisect(dp,x)
    if i == len(dp):
        dp.append(x)    
    else:            
        dp[i] = min(dp[i],x)
print(len(dp))

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

Solution (Python):
import sys
aa=list(map(int,sys.stdin.read().split()))
aa=aa[1:aa[0]+1]
n=len(aa)
import bisect
bb=[]
for i in range(n):
    if not bb:
        bb.append(aa[-i-1])
    else:
        if bb[-1] <= aa[-i-1]:
            bb.append(aa[-i-1])
        else:
            j = bisect.bisect_right(bb,aa[-i-1])
            bb[j] = aa[-i-1]
print(len(bb))

Solution (Python):


 
import sys
import math
import bisect
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
mod = 10**9 + 7
 
n = int(input())
a = [int(input()) for _ in range(n)]
m = []
for i in range(n):
    r = bisect.bisect_right(m,-a[i])
    if r == len(m):
        m.append(-a[i])
    else:
        m[r] = -a[i]
print(len(m))

Solution (Python):
from bisect import*
n,*a=map(int,open(0))
b=bisect
c=[-1]*n
for a in a:c[b(c,a-1)-1]=a
print(n-b(c,-1))

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


def IN_S():
  return input()


def IN_I():
  return int(input())


def IN_L_I():
  return list(map(int, input().split()))


def IN_L_S():
  return list(map(str, input().split()))


def STR_SPLIT(s, n):
  for l in range(0, len(s), n):
    yield s[0 + l:n + l]


def T_IN():
  global test_str
  sys.stdin = io.StringIO(test_str[1:-1])


test_str = '''
7
1
0
3
4
1
2
1
'''


def MAIN():
  
  A()


def A():
  n = IN_I()

  l = deque([IN_I()])

  for i in range(0, n - 1):
    num = IN_I()

    idx = bisect_left(l, num)
    if idx == 0:
      l.appendleft(num)
    else:
      l[idx - 1] = num
    

  print(len(l))
  return None


def B():
  return None


def C():
  return None


MAIN()

Solution (Python):
import bisect as bs
N = int(input())
A = [int(input()) for _ in range(N)]
def LDS(a):
    N = len(a)
    INF = float("inf")
    dp = [-INF]*N
    dp[N-1] = a[0]
    for i in range(1, N):
        j = bs.bisect_left(dp, a[i])-1
        dp[j] = a[i]
    for i in range(N-1, -1, -1):
        if dp[i] == -INF:
            return N-i-1
    return N
print(LDS(A))

Solution (Python):
from bisect import bisect_left
from collections import deque
N = int(input())
A = [int(input()) for i in range(N)]
cnt, ms, flag = 1, deque(), 1
ms.append(A[0])
for a in A[1:]:
    if a <= ms[0]:
        ms.appendleft(a)
        cnt += 1
    else:
        i = bisect_left(ms, a)-1
        ms[i] = a
print(cnt)

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


def LIS(arr):
    N = len(arr)
    dp = [inf] * N
    res = 0
    for a in arr:
        pos = bisect(dp,a)
        dp[pos] = a
        res = max(res, pos + 1)
    return res

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

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

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

def main():
    input = sys.stdin.readline
    N = int(input())
    A = deque([int(input())])
    for k in range(N-1):
        t = int(input())
        if A[0] >= t:
            A.appendleft(t)
        else:
            A[bisect.bisect_left(A,t)-1] = t
    print(len(A))

if __name__ == '__main__':
    main()

Solution (Python):



import sys
import math
import bisect
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
mod = 10**9 + 7

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

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

print(len(tmp))

Solution (Python):
from bisect import*
n,*a=map(int,open(0))
b=[-1]*n
for a in a:b[bisect(b,a-1)-1]=a
print(n-b.count(-1))

Solution (Python):
from bisect import*
n,*a=map(int,open(0))
b=[-1]*n
for a in a:b[bisect(b,a-1)-1]=a
print(n-b.count(-1))

Solution (Python):

import bisect

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


LIS = list()
for i in a:
    j = bisect.bisect_right(LIS, i)
    if len(LIS) == j:
        LIS.append(i)
    else:
        LIS[j] = i

print(len(LIS))

Solution (Python):
from collections import deque
import bisect

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

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

Solution (Python):
import sys
input = sys.stdin.readline
from collections import deque
from bisect import bisect_right, bisect_left
def main():
    N = int( input())
    A = [ int( input()) for _ in range(N)]
    d = deque()
    for a in A:
        t = bisect_right(d, a)
        if t == 0:
            d.appendleft(a)
            continue
        if d[t-1] == a:
            t = bisect_left(d, a)
        if t == 0:
            d.appendleft(a)
        else:
            d[t-1] = a
    print(len(d))

if __name__ == '__main__':
    main()

Solution (Python):
import sys
input = sys.stdin.readline
from collections import deque
from bisect import bisect_right, bisect_left
def main():
    N = int( input())
    A = [ int( input()) for _ in range(N)]
    d = deque()
    for a in A:
        t = bisect_right(d, a)
        if t == 0:
            d.appendleft(a)
            continue
        if d[t-1] == a:
            t = bisect_left(d, a)
        if t == 0:
            d.appendleft(a)
        else:
            d[t-1] = a
    print(len(d))

if __name__ == '__main__':
    main()

Solution (Python):


from collections import deque
from bisect import bisect_right, bisect_left
def main():
    N = int( input())
    A = [ int( input()) for _ in range(N)]
    d = deque()
    for a in A:
        t = bisect_right(d, a)
        if t == 0:
            d.appendleft(a)
            continue
        if d[t-1] == a:
            t = bisect_left(d, a)
        if t == 0:
            d.appendleft(a)
        else:
            d[t-1] = a
    print(len(d))
if __name__ == '__main__':
    main()

Solution (Python):


from collections import deque
from bisect import bisect_right, bisect_left
def main():
    N = int( input())
    A = [ int( input()) for _ in range(N)]
    d = deque()
    for a in A:
        t = bisect_right(d, a)
        if t == 0:
            d.appendleft(a)
            continue
        if d[t-1] == a:
            t = bisect_left(d, a)
        if t == 0:
            d.appendleft(a)
        else:
            d[t-1] = a
    print(len(d))
if __name__ == '__main__':
    main()

Solution (Python):
n = int(input())
an = [0]*n
for i in range(0, n):
    an[i] = int(input())
dp = [-1] * n

len = 1
dp[0] = an[0]
for i in range(1,n):
    if dp[len-1] >= an[i]:
        dp[len] = an[i]
        len += 1
        continue
    
    idx = len // 2
    r = len-1
    l = 0
    while(True):
        if dp[idx] >= an[i]:
            if r == idx+1:
                dp[r] = an[i]
                break
            else:
                l = idx
                idx = idx + (r - idx) // 2
        else:
            if l == idx:
                dp[l] = an[i]
                break
            else:
                r = idx
                idx = l + (idx - l) // 2
    
print(len)

Solution (Python):
from collections import deque
import bisect

def solve():
  N = int(input())
  A = [int(input()) for i in range(N)]
  q = deque()
  for a in A:
    if len(q) == 0 or a <= q[0]:
      q.appendleft(a)
    else:
      q[bisect.bisect_left(q, a) - 1] = a

  return len(q)

print(solve())

Solution (Python):
import bisect

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

dp = [INF for i in range(N+1)]


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

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

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

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

ans = len(color)
print(ans)