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

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

l = deque([])

for i in range(N):
    if l == []:
        l.append(A[i])
    else:
        index = bisect.bisect_right(l, A[i])
        index2 = bisect.bisect_left(l, A[i])
        if index == 0:
            l.appendleft(A[i])
        elif index != index2:
            if index2 == 0:
                l.appendleft(A[i])
            else:
                l[index2-1] = A[i]
        else:
            l[index-1] = A[i]

print(len(l))

Solution (Python):

import sys
from collections import deque, defaultdict
import copy
import bisect
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 9)

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

B = []
min = -10000000000
for i in range(N):
	loc = bisect.bisect_right(B, -A[i])
	if loc == len(B):
		B.append(-A[i])
	else:
		B[loc] = -A[i]

print(len(B))

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

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

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

Solution (Python):
import bisect

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

x = [A[0]]

for a in A[1:]:
    i = bisect.bisect(x,a)
    if i==len(x): x.append(a)
    else: x[i]=a

print(len(x))

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

tree = deque([[A[0]]])
leaf = deque([A[0]])
for n in range(1,N):
    a = A[n]
    pos = min(n-1,bisect.bisect_left(leaf,a)-1)
    if pos==-1:
        tree.appendleft([a])
        leaf.appendleft(a)
    else:
        tree[pos].append(a)
        leaf[pos] = a
print(len(tree))

Solution (Python):

def binSearch(S, x):
    a = -1
    b = len(S)-1

    while(a + 1 < b):
        c = (a+b)//2
        if S[c] >= x:
            a = c
        else:
            b = c

    return b

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

    S = []

    for a in A:
        if len(S) == 0 or S[-1] >= a:
            S.append(a)
        else:
            p = binSearch(S, a)
            S[p] = a
    
    print(len(S))


if __name__ == '__main__':
    main()

Solution (Python):
from heapq import *
from bisect import bisect_right, bisect_left
from collections import deque
N = int(input())
A = [int(input()) for i in range(N)]
lb, ub = 0, N
while lb + 1 < ub:
    mid = (lb+ub)//2
    cnt, ms, flag = 1, deque(), 1
    ms.append(A[0])
    for a in A[1:]:
        if a <= ms[0]:
            ms.appendleft(a)
            cnt += 1
            if cnt > mid:
                flag = 0
                break
        else:
            i = bisect_left(ms, a)-1
            ms[i] = a
    if flag:
        ub = mid
    else:
        lb = mid
cnt, ms, flag = 1, deque(), 1
ms.append(A[0])
for a in A[1:]:
    if a <= ms[0]:
        ms.appendleft(a)
        cnt += 1
        if cnt > mid:
            flag = 0
            break
    else:
        i = bisect_left(ms, a)-1
        ms[i] = a
if flag:
    print(mid)
else:
    print(mid+1)

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

N = int(input())
L = [-1 * int(input())]
for _ in range(N - 1):
    a = -1 * int(input())
    if a >= L[-1]:
        L.append(a)
        continue

    i = bisect.bisect_right(L, a)
    L[i] = a

print(len(L))

Solution (Python):
N = int(input())
A = [int(input()) for _ in [0]*N]
B = [A[0]]
ans = 1

for a in A[1:]:
    l = 0
    r = ans - 1
    if B[0]<a:r=0
    while l+1<r:
        i = (l+r)//2
        if B[i] < a:
            r = i
        else:
            l = i
    if B[r]<a:B[r] = a
    else:
        B.append(a)
        ans += 1
print(ans)

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

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

list_ = deque([As[0]])
for a in As[1:]:
    i = bisect_left(list_, a) - 1
    if i < 0:
        list_.appendleft(a)
    else:
        list_[i] = a
print(len(list_))

Solution (Python):
import sys, math
from collections import deque

readline = sys.stdin.readline

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


heads = []

for a in A:
    if len(heads) == 0:
        heads.append(a)
    else:
        left = 0
        right = len(heads) - 1
        while right - 1 > left:
            mid = (left + right) // 2
            if a <= heads[mid]:
                left = mid + 1
            else:
                right = mid

        if a > heads[left]:
            heads[left] = a
        elif a > heads[right]:
            heads[right] = a
        else:
            heads.append(a)

print(len(heads))

Solution (Python):
import bisect

n=int(input())
a1=int(input())
alist=[]
for al in range(n-1):
    alist.append(-2)
alist.append(a1)

for i in range(n-1):
    an=int(input())
    
    index = bisect.bisect_left(alist, an)
    alist[index-1]=an


index = bisect.bisect_left(alist, -1)

print(len(alist)- index)

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

from bisect import bisect

h = []

for ai in a:

    ix = bisect(h, -ai)
    if ix == len(h):
        h.append(-ai)
    else:
        h[ix] = -ai

print(len(h))

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
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 II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7

debug = True
debug = False

def dprint(*objects):
    if debug == True:
        print(*objects)

def main():
    N = II()
    a_list = []

    for i in range(N):
        a = II()
        a_list.append(a)


    from bisect import bisect_left
    from collections import deque
    g = deque()

    for i in range(N):
        a = a_list[i]
        if len(g) == 0:
            g.appendleft(a)
        else:
            pos = bisect_left(g, a)
            dprint(g, a, pos)
            if pos >= 1:
                g[pos-1] = a
            else:
                
                g.appendleft(a)
    dprint(g)
    print(len(g))
main()

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

def I(): return int(sys.stdin.readline())

def main():
  n = I()
  a = [I() for i in range(n)]
  b = []

  for i in range(n-1, -1, -1):
    t = bisect_right(b, a[i])
    if len(b)-1<t or b[t]==a[i]:
      insort(b, a[i])
    else:
      b[t] = a[i]
  print(len(b))

if __name__ == '__main__':
  main()

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

def I(): return int(sys.stdin.readline())

def main():
  n = I()
  a = [I() for i in range(n)]
  b = []

  for i in range(n-1, -1, -1):
    t = bisect_right(b, a[i])
    if len(b)-1<t or b[t]==a[i]:
      insort(b, a[i])
    else:
      b[t] = a[i]
  print(len(b))

if __name__ == '__main__':
  main()

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

from bisect import bisect_right
	
def LIS(L) :   
    lis = [L[0]]
    for a in L[1:] :
        if a >= lis[-1] :
            lis.append(a)
        else :
            s = bisect_right(lis, a)
            lis[s] = a
    return len(lis)

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

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

n = int(input())
f = int(input())
ans = [-f]
for i in range(n-1):
    now = -int(input())
    j = bisect_right(ans,now)
    if j == len(ans):
        ans.append(now)
    else:
        ans[j] = now

print(len(ans))

Solution (Python):
from bisect import bisect_left


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


if __name__ == "__main__":
    n = int(input())
    a_list = [int(input()) for _ in range(n)]

    color_list = [-1] * n
    color_num = 0

    for a in a_list:
        
        index = bisect_left(color_list, a)
        
        color_list[index - 1] = a
        if n - index == color_num:
            color_num = color_num + 1
        
    
    
    print(color_num)

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

B = [A[0]]

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

Solution (Python):
import bisect
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  

n = ni()
a = []
for i in range(n):
    a.append(ni())
a = a[::-1]
hs = [999999999999] * (n+1)
lis = 0
for v in a:
    pos = bisect.bisect_right(hs, v)
    hs[pos] = v
    lis = max(lis, pos+1)
print(lis)

Solution (Python):
import bisect
from collections import deque


n = int(input())
lines = deque()
for _ in range(n):
    a = int(input())

    index = bisect.bisect_left(lines, a)
    if index == 0:
        lines.appendleft(a)
        continue
    
    lines[index - 1] = a

print(len(lines))

Solution (Python):
import sys
from bisect import bisect_right, insort_left
from collections import deque
N = int(sys.stdin.readline())
a_list = [int(sys.stdin.readline()) for _ in range(N)]


que = []
que = deque(que)

ans = 0
min_num = float("inf")
for i, a in enumerate(a_list):
    if i == 0:
        que.append(a)
        min_num = a
        ans += 1
    else:
        idx = bisect_right(que, a-1)

        if idx == 0:
            que.appendleft(a)
            ans += 1
            min_num = a
        else:
            idx = bisect_right(que, a-1)
            que[idx-1] = a
            if idx -1 == 0:
                min_num = a
    
print(ans)

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 heapq import heapify, heappush, heappop, heappushpop  

def main():
    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))

main()

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

Solution (Python):



import sys  
import os
import time
import re
from pydoc import help
import string
import math
from operator import itemgetter
from collections import Counter
from collections import deque
from collections import defaultdict as dd
import fractions
from heapq import heappop, heappush, heapify
import array
from bisect import bisect_left, bisect_right, insort_left, insort_right
from copy import deepcopy as dcopy
import itertools



sys.setrecursionlimit(10**7)
INF = 10**20
GOSA = 1.0 / 10**10
MOD = 10**9+7
ALPHABETS = [chr(i) for i in range(ord('a'), ord('z')+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 DP(N, M, first): return [[first] * M for n in range(N)]
def DP3(N, M, L, first): return [[[first] * L for n in range(M)] for _ in range(N)]
from inspect import currentframe


def local_input():
    from pcm.utils import set_stdin
    import sys
    from pathlib import Path
    parentdir = Path(os.path.dirname(__file__)).parent
    inputfile = parentdir.joinpath('test/sample-1.in')
    if len(sys.argv) == 1:
        set_stdin(inputfile)


def solve():
    n = int(input())
    a = []
    
    col = 1

    for _ in range(n):
        a.append(-int(input()))
    
    if n == 1:
        print(col)
        exit()

    b = [a[0]]
    m = 1

    for i in range(1,n):
        x = bisect_right(b,a[i])
        
        if x == m:
            col += 1
            b.append(a[i])
            m += 1
        else:
            b[x] = a[i]
        
    print(col)

    return 0

if __name__ == "__main__":
    try:
        local_input()
        def dump(*args):
            names = {id(v):k for k,v in currentframe().f_back.f_locals.items()}
            print(', '.join(names.get(id(arg),'???')+' => '+repr(arg) for arg in args), file=sys.stderr)
    except:
        def dump(*args):
            pass

    solve()

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

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

ans = [a[0]]

for i in range(1, N):

    if  ans[len(ans) - 1] >= a[i]:
        ans.append(a[i])
    elif ans[0] < a[i]:
        ans[0] = a[i]
    elif ans[len(ans) - 2] >= a[i]:
        ans[len(ans) - 1] = a[i]
    else:
        l = 0
        h = len(ans) - 1
        m = (l + h) // 2
        while True:
            if ans[m] >= a[i]:
                l = m
                m = (l + h) // 2
                continue

            if ans[m - 1] < a[i]:
                h = m
                m = (l + h) // 2
                continue
            break
        ans[m] = a[i]

print(len(ans))

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

Solution (Python):

import copy
import random
import bisect 
import fractions 
import math
import sys
import bisect
from collections import deque

mod = 10**9+7
sys.setrecursionlimit(mod) 

def LI(): return list(map(int, sys.stdin.readline().split()))
N = int(input())
A = [0 for i in range(N)]
for i in range(N):
    A[i] = int(input())

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

print(ans)

Solution (Python):
N = int(input())
As = []
for i in range(N):
  A = int(input())
  As.append(A)
def find2(s, A):
  import math
  a = 0
  b = len(s)
  while a < b:
    i = (a+b)//2
    if s[i] < A:
      b = i
    else:
      if a == i:
        break
      a = i
  return b

num = 1
c = As[0]
s = [c]
for i in range(1,N):
  A = As[i]
  index = find2(s, A)
  
  
  
  
  
  
  if index < len(s):
    
    s[index] = A
  else:
    
    num += 1
    s.append(A)
    c = A
print(num)

Solution (Python):
def main():

    """ convenient functions
    
    
    
    
    
    """

    """convenient decorator
    
    
        
        
        
        
        
        
        
        
        
        
    """
    
    
    import sys
    sys.setrecursionlimit(10**7)
    from itertools import accumulate, combinations, permutations, product 
    
    from math import factorial, ceil, floor, sqrt
    def factorize(n):
        """return the factors of the Arg and count of each factor
        
        Args:
            n (long): number to be resolved into factors
        
        Returns:
            list of tuples: factorize(220) returns [(2, 2), (5, 1), (11, 1)]
        """
        fct = []  
        b, e = 2, 0  
        while b * b <= n:
            while n % b == 0:
                n = n // b
                e = e + 1
            if e > 0:
                fct.append((b, e))
            b, e = b + 1, 0
        if n > 1:
            fct.append((n, 1))
        return fct
    def combinations_count(n, r):
        """Return the number of selecting r pieces of items from n kinds of items.
        
        Args:
            n (long): number
            r (long): number
        
        Raises:
            Exception: not defined when n or r is negative
        
        Returns:
            long: number
        """
        
        if n < 0 or r < 0:
            raise Exception('combinations_count(n, r) not defined when n or r is negative')
        if n - r < r: r = n - r
        if r < 0: return 0
        if r == 0: return 1
        if r == 1: return n
        numerator = [n - r + k + 1 for k in range(r)]
        denominator = [k + 1 for k in range(r)]
        for p in range(2,r+1):
            pivot = denominator[p - 1]
            if pivot > 1:
                offset = (n - r) % p
                for k in range(p-1,r,p):
                    numerator[k - offset] /= pivot
                    denominator[k] /= pivot
        result = 1
        for k in range(r):
            if numerator[k] > 1:
                result *= int(numerator[k])
        return result
    def combinations_with_replacement_count(n, r):
        """Return the number of selecting r pieces of items from n kinds of items allowing individual elements to be repeated more than once.
        
        Args:
            n (long): number
            r (long): number
        
        Raises:
            Exception: not defined when n or r is negative
        
        Returns:
            long: number
        """
        if n < 0 or r < 0:
            raise Exception('combinations_with_replacement_count(n, r) not defined when n or r is negative')
        elif n == 0:
            return 1
        else:
            return combinations_count(n + r - 1, r)
    from bisect import bisect_left, bisect_right
    from collections import deque, Counter, defaultdict 
    from heapq import heapify, heappop, heappush, heappushpop, heapreplace,nlargest,nsmallest 
    from copy import deepcopy, copy 
    import operator
    from operator import itemgetter
    
    
    from functools import reduce, lru_cache
    def chmin(x, y):
        """change minimum
        if x > y, x = y and return (x, True).
        convenient when solving problems of dp[i]
        
        Args:
            x (long): current minimum value
            y (long): potential minimum value
        
        Returns:
            (x, bool): (x, True) when updated, else (x, False)
        """
        if x > y:
            x = y
            return (x, True)
        else:
            return (x, False)
    def chmax(x, y):
        """change maximum
        if x < y, x = y and return (x, True).
        convenient when solving problems of dp[i]
        
        Args:
            x (long): current maximum value
            y (long): potential maximum value
        
        Returns:
            (x, bool): (x, True) when updated, else (x, False)
        """
        if x < y:
            x = y
            return (x, True)
        else:
            return (x, False)

    from fractions import gcd 
    def gcds(numbers):
        return reduce(gcd, numbers)
    def lcm(x, y):
        return (x * y) // gcd(x, y)
    def lcms(numbers):
        return reduce(lcm, numbers, 1)

    
    
    INF = 10 ** 18
    MOD = 10 ** 9 + 7
    modpow = lambda a, n, p = MOD: pow(a, n, p) 
    def modinv(a, p = MOD):
        
        
        return modpow(a, p-2, p)
    def modinv_list(n, p = MOD):
        if n <= 1:
            return [0,1][:n+1]
        else:
            inv_t = [0,1]
            for i in range(2, n+1):
                inv_t += [inv_t[p % i] * (p - int(p / i)) % p]
            return inv_t
    def modfactorial_list(n, p = MOD):
        if n == 0:
            return [1]
        else:
            l = [0] * (n+1)
            tmp = 1
            for i in range(1, n+1):
                tmp = tmp * i % p
                l[i] = tmp
            return l
    def modcomb(n, k, fac_list = [], p = MOD):
        
        
        from math import factorial
        if n < 0 or k < 0 or n < k: return 0
        if n == 0 or k == 0: return 1
        if len(fac_list) <= n:
            a = factorial(n) % p
            b = factorial(k) % p
            c = factorial(n-k) % p
        else:
            a = fac_list[n]
            b = fac_list[k]
            c = fac_list[n-k]
        return (a * modpow(b, p-2, p) * modpow(c, p-2, p)) % p
    def modadd(a, b, p = MOD):
        return (a + b) % MOD
    def modsub(a, b, p = MOD):
        return (a - b) % p
    def modmul(a, b, p = MOD):
        return ((a % p) * (b % p)) % p
    def moddiv(a, b, p = MOD):
        return modmul(a, modpow(b, p-2, p))

    """ initialize variables and set inputs
    
        
        
    
        
        
        
        
        
    
        
        
        
        
    
        
        
    """

    
    r = lambda: sys.stdin.readline().strip()
    r_int = lambda: int(r())
    R = lambda: list(map(int, r().split()))
    Rmap = lambda: map(int, r().split())
    Rfloat = lambda: list(map(float, r().split()))
    Rtuple = lambda: tuple(map(int, r().split()))

    """ how to treat input
    
    
    
    
    
    
    
    """

    if __name__ != '__main__':
        
        sys.stdin = open('sample.txt')

    
    

    N = int(r())
    A = [-int(r()) for _ in range(N)]
    B = [INF]
    length = 1
    for a in A:
        tmp = bisect_right(B, a)
        if tmp == length:
            B.append(a)
            length += 1
        else:
            B[tmp] = a
    print(length)
    
    

    """memo: how to use defaultdict of list
    
    Dic = defaultdict(list)
    
    Dic[x].append(y)
    
    for k, v in Dic.items():
    """

if __name__ == '__main__':
    main()

Solution (Python):
import bisect
from collections import deque
N = int(input())
A = [int(input()) for i in [0]*N]


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

print(len(ls))

Solution (Python):
import bisect
from collections import deque

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


def colorfind(a, colors):
    index = bisect.bisect_left(colors, a)
    return index


color = deque([])
for i in range(n):
    if i == 0:
        color.appendleft(a[i])
    elif color[0] >= a[i]:
        color.appendleft(a[i])
    else:
        colorindex = colorfind(a[i], color)
        color[colorindex - 1] = a[i]

print(len(color))

Solution (Python):
from collections import defaultdict

N = int(input())
A = [int(input()) for i in range(N)]
d = defaultdict(lambda: [])
for i,a in enumerate(A):
    d[a].append(i)
B = [None for i in range(N)]
for i,k in enumerate(sorted(d.keys())):
    for j in d[k]:
        B[j] = i

bit = [0] * (N+2)
def bit_add(a,w):
    x = a
    while x <= N+1:
        bit[x] += w
        x += (x & -x)

def bit_sum(a):
    x = a
    ret = 0
    while x > 0:
        ret += bit[x]
        x -= (x & -x)
    return ret

for a in B:
    a += 2

    s = bit_sum(a)
    bit_add(a,1)
    if s and bit_sum(a-1):
        t = bit_sum(a-1)
        ok = a-1
        ng = 0
        while ok-ng > 1:
            m = (ok+ng)//2
            if bit_sum(m) == t:
                ok = m
            else:
                ng = m
        bit_add(ok,-1)

    
    

print(bit_sum(N+1))

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

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


N=int(input())
A=[int(input()) for i in range(N)]
s=[A[-1]]
for i in range(N-2,-1,-1):
    k=br(s,A[i])
    if len(s)==k:
        s.append(A[i])
    else:
        s[k]=A[i]
print(len(s))

Solution (Python):

def bisect(a,B,lo,hi):
    if hi-lo<=1:
        return hi
    elif B[(hi+lo)//2]>=a:
        return bisect(a,B,(hi+lo)//2,hi)
    else:
        return bisect(a,B,lo,(hi+lo)//2)

N = int(input())

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

B = [A[0]]

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

Solution (Python):

import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline


def read_int():
    return int(input())


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


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


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap



def slv(N, A):
    
    L = [-A.pop(0)]
    ma = L[0]
    for a in A:
        if ma <= -a:
            ma = -a
            L.append(ma)
            continue
        i = bisect.bisect_right(L, -a)
        L[i] = -a
        ma = L[-1]
    return len(L)



def main():
    N = read_int()
    A = [read_int() for _ in range(N)]
    print(slv(N, A))


if __name__ == '__main__':
    main()

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

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

print(len(res))

Solution (Python):
import heapq as hq
N = int(input())
peak = []
peak_num = 0

def search(lst, n, length):
	l = 0
	r = length
	while r - l > 1:
		p = (l+r) // 2
		if lst[p] < n:
			r = p
		else:
			l = p
	return l

for i in range(N):
	a = int(input())
	if peak_num == 0:
		peak.append(a)
		peak_num += 1
	elif peak[peak_num-1] >= a:
		peak.append(a)
		peak_num += 1
	else:
		n = search(peak, a, peak_num)
		if peak[n] < a:
			peak[n] = a
		else:
			peak[n+1] = a
print(peak_num)

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

def solve():
    input = sys.stdin.readline
    N = int(input())
    A = [int(input()) for _ in range(N)]
    col = [1] * N
    col[0] = -A[0]
    for a in A[1:]:
        index = bisect_right(col, -a)
        col[index] = -a
        
    ans = bisect_right(col, 0)
    print(ans)

    return 0

if __name__ == "__main__":
    solve()

Solution (Python):
import bisect
N = int(input())
A = [int(input())for _ in range(N)]
li = [-1]
for i in A[::-1]:
    if(li[-1]<i):
        li.append(i)
    else:
        ind = bisect.bisect_right(li,i)
        if(ind>=len(li)):
            li.append(i)
        elif(li[ind]>i):
            li.pop(ind)
            li.insert(ind,i)
        else:
            li.pop(ind+1)
            li.insert(ind+1)
print(len(li)-1)

Solution (Python):
from bisect import bisect_left as bs
from collections import deque
N=int(input())
pallet=deque()
cnt=0
for _ in range(N):
    A=int(input())
    place=bs(pallet,A)
    if place==0:
        cnt+=1
        pallet.appendleft(A)
    else:
        pallet[place-1]=A
print(cnt)

Solution (Python):
def bin_search(temp, x, start, end):
	
	ind = -1
	while start <= end:
		middle = (start + end)//2
		
		if x > temp[middle]:
			ind = middle
			end = middle-1
		else:
			start = middle+1
	
	if ind == -1:
		temp += [x]
	else:
		temp[ind] = x




n = int(input())
arr = []
for i in range(n):
	arr += [int(input())]

temp = [arr[0]]
arr.pop(0)
for x in arr:
	bin_search(temp, x, 0, len(temp)-1)

print(len(temp))

Solution (Python):
import bisect


def main():
  x = [int(input()) for _ in range(int(input()))]
  c = [x[-1]]

  for i in range(len(x) - 2, -1, -1):
    j = bisect.bisect(c, x[i])

    if j == len(c):
      c.append(x[i])
    else:
      c[j] = x[i]

  print(len(c))


if __name__ == '__main__':
  main()

Solution (Python):
import bisect

N = int(input())
L = []
L.append(-int(input()))
c = 1

for i in range(N - 1):
	A = -int(input())
	x = bisect.bisect_right(L, A)
	if x == c:
		L.append(A)
		c += 1
	else:
		L[x] = A

print(c)