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 sys
from bisect import bisect_left, bisect_right
from collections import deque




n = int(sys.stdin.readline())
L = [int(sys.stdin.readline()) for i in range(n)]
IS = deque([L[0]])
for i in range(1, n):
    if L[i] <= IS[0]:
        IS.appendleft(L[i])
    else:
        IS[bisect_left(IS, L[i]) - 1] = L[i]



print(len(IS))

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



sys.setrecursionlimit(2147483647)
INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


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



print(len(IS))

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


def bi(a, x):
    i, j = 0, len(a) - 1
    while i != j:
        k = (i + j) // 2
        if a[k] >= x:
            i = k+1
        else:
            j = k
    if a[-1] >= x:
        i =-1
    return i


for i in a:
    j = bi(b, i)
    if j == -1:
        b.append(i)
        c += 1
    else:
        b[j] = i
print(c)

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

Solution (Python):
from bisect import bisect_right, bisect_left

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

dp = [1]*N

for a in A:
    ia = bisect_right(dp, -a)
    if dp[ia] == 1:
        dp[ia] = -a
    else:
        ib = bisect_left(dp, -a+1)
        dp[ib] = -a
    

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

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

Solution (Python):
import bisect

N = int(input())

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

B = [A[0]]

for j in range(1,N):
    if B[-1] <= A[j]:
        B.append(A[j])
    else:
        B[bisect.bisect_right(B,A[j])] = A[j]
    

print(len(B))

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

from bisect import *

h = []

for a in A:
    x = bisect_right(h, -a)
    if len(h) <= x:
        h.append(-a)
    else:
        h[x] = -a

result = len(h)

print(result)

Solution (Python):

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

C = []
for i in range(N):
    if i == 0:
        C.append(A[i])
    else:
        li = bisect.bisect_right(C,A[i])
        if li == len(C):
            C.append(A[i])
        else:
            C[li] = A[i]
    
print(len(C))

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

for _ in range(n):
    a = int(input())
    if len(q) == 0:
        q.appendleft(a)
    elif a <= q[0]:
        q.appendleft(a)
    else:
        i = bisect.bisect_right(q, a-1) - 1
        q[i] = a
print(len(q))

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

Solution (Python):
class Multiset:
    def __init__(self, N):
        self.N = N
        self.tree = [0] * (N + 1)
        self.bisect_K = [1 << k for k in reversed(range(N.bit_length()))]

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def bisect(self, w):
        if w <= 0:
            return 0
        bit, N = self.tree, self.N
        i = 0
        for k in self.bisect_K:
            ni = i + k
            if ni <= N and bit[ni] < w:
                w -= bit[ni]
                i = ni
        return i + 1

    def insert(self, i):
        while i <= self.N:
            self.tree[i] += 1
            i += i & -i

    def erase(self, i):
        while i <= self.N:
            self.tree[i] -= 1
            i += i & -i

    def lower_bound(self, x):
        return self.bisect(self.sum(x))

    def size(self):
        return self.sum(self.N)


def main():

    

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

    memo = {a: i for i, a in enumerate(sorted(set(A)), 1)}
    M = len(memo)

    ms = Multiset(M)
    for b in (memo[a] for a in A):
        i = ms.lower_bound(b - 1)
        if i != 0:
            ms.erase(i)
        ms.insert(b)

    print(ms.size())


if __name__ == '__main__':
    main()

Solution (Python):
class Multiset:
    def __init__(self, N):
        self.N = N
        self.tree = [0] * (N + 1)
        self.bisect_K = [1 << k for k in reversed(range(N.bit_length()))]

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.N:
            self.tree[i] += x
            i += i & -i

    def bisect(self, w):
        if w <= 0:
            return 0
        bit, N = self.tree, self.N
        i = 0
        for k in self.bisect_K:
            ni = i + k
            if ni <= N and bit[ni] < w:
                w -= bit[ni]
                i = ni
        return i + 1

    def insert(self, x):
        self.add(x, 1)

    def erase(self, x):
        self.add(x, -1)

    def lower_bound(self, x):
        return self.bisect(self.sum(x))

    def size(self):
        return self.sum(self.N)


def main():

    

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

    memo = {a: i for i, a in enumerate(sorted(set(A)), 1)}
    M = len(memo)

    ms = Multiset(M)
    for b in (memo[a] for a in A):
        i = ms.lower_bound(b - 1)
        if i != 0:
            ms.erase(i)
        ms.insert(b)

    print(ms.size())


if __name__ == '__main__':
    main()

Solution (Python):
class BIT:
    def __init__(self, N):
        self.size = N
        self.tree = [0] * (N + 1)
        self.bisect_K = [1 << k for k in reversed(range(N.bit_length()))]

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

    def bisect(self, w):
        if w <= 0:
            return 0
        bit, N = self.tree, self.size
        i = 0
        for k in self.bisect_K:
            ni = i + k
            if ni <= N and bit[ni] < w:
                w -= bit[ni]
                i = ni
        return i + 1


class Multiset:
    def __init__(self, N):
        self.N = N
        self.bit = BIT(N)

    def insert(self, x):
        self.bit.add(x, 1)

    def erase(self, x):
        self.bit.add(x, -1)

    def lower_bound(self, x):
        return self.bit.bisect(self.bit.sum(x))

    def size(self):
        return self.bit.sum(self.N)

def main():

    

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

    memo = {a: i for i, a in enumerate(sorted(set(A)), 1)}
    M = len(memo)

    ms = Multiset(M)
    for b in (memo[a] for a in A):
        i = ms.lower_bound(b - 1)
        if i != 0:
            ms.erase(i)
        ms.insert(b)

    print(ms.size())


if __name__ == '__main__':
    main()

Solution (Python):
class BIT:
    def __init__(self, N):
        self.size = N
        self.tree = [0] * (N + 1)
        self.bisect_K = [1 << k for k in reversed(range(N.bit_length()))]

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

    def bisect(self, w):
        if w <= 0:
            return 0
        bit, N = self.tree, self.size
        i = 0
        for k in self.bisect_K:
            if i + k <= N and bit[i + k] < w:
                i += k
                w -= bit[i]
        return i + 1


class Multiset:
    def __init__(self, N):
        self.N = N
        self.bit = BIT(N)

    def insert(self, x):
        self.bit.add(x, 1)

    def erase(self, x):
        self.bit.add(x, -1)

    def lower_bound(self, x):
        return self.bit.bisect(self.bit.sum(x))

    def size(self):
        return self.bit.sum(self.N)


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

memo = {a: i for i, a in enumerate(sorted(set(A)), 1)}
M = len(memo)

ms = Multiset(M)
for b in (memo[a] for a in A):
    i = ms.lower_bound(b - 1)
    if i != 0:
        ms.erase(i)
    ms.insert(b)

print(ms.size())

Solution (Python):
class BIT:
    def __init__(self, N):
        self.size = N
        self.tree = [0] * (N + 1)
        self.bisect_K = [1 << k for k in reversed(range(N.bit_length()))]

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

    def bisect(self, w):
        if w <= 0:
            return 0
        bit, N = self.tree, self.size
        i = 0
        for k in self.bisect_K:
            if i + k <= N and bit[i + k] < w:
                i += k
                w -= bit[i]
        return i + 1


class Multiset:
    def __init__(self, N):
        self.N = N
        self.bit = BIT(N)

    def insert(self, x):
        self.bit.add(x, 1)

    def erase(self, x):
        self.bit.add(x, -1)

    def lower_bound(self, x):
        return self.bit.bisect(self.bit.sum(x))

    def size(self):
        return self.bit.sum(self.N)


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

memo = {a: i for i, a in enumerate(sorted(set(A)), 1)}
M = len(memo)

ms = Multiset(M)
for b in (memo[a] for a in A):
    i = ms.lower_bound(b - 1)
    if i != 0:
        ms.erase(i)
    ms.insert(b)

print(ms.size())

Solution (Python):
class BIT:
    def __init__(self, N):
        self.size = N
        self.tree = [0] * (N + 1)
        self.bisect_K = [1 << k for k in reversed(range(N.bit_length()))]

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

    def bisect(self, w):
        bit, N = self.tree, self.size
        i = 0
        for k in self.bisect_K:
            if i + k <= N and bit[i + k] < w:
                i += k
                w -= bit[i]
        return i + 1


class Multiset:
    def __init__(self, N):
        self.N = N
        self.bit = BIT(N)

    def insert(self, x):
        self.bit.add(x, 1)

    def erase(self, x):
        self.bit.add(x, -1)

    def lower_bound(self, x):
        s = self.bit.sum(x)
        return self.bit.bisect(s) if s else 0

    def size(self):
        return self.bit.sum(self.N)


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

memo = {a: i for i, a in enumerate(sorted(set(A)), 1)}
M = len(memo)

ms = Multiset(M)
for b in (memo[a] for a in A):
    i = ms.lower_bound(b - 1)
    if i != 0:
        ms.erase(i)
    ms.insert(b)

print(ms.size())

Solution (Python):
import bisect
def main():

    N = int(input())
    A = []
    for _ in range(N):
        A.append(int(input()))
    B = [A[-1]]
    for i in range(N-2, -1, -1):
        if B[-1] <= A[i]:
            B.append(A[i])
        else:
            j = bisect.bisect_right(B, A[i])
            B[j] = A[i]
    return len(B)

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

Solution (Python):
class BIT:
    def __init__(self, N):
        self.size = N
        self.tree = [0] * (N + 1)
        self.bisect_K = [1 << k for k in reversed(range(N.bit_length()))]

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

    def bisect(self, w):
        bit, N = self.tree, self.size
        i = 0
        for k in self.bisect_K:
            if i + k <= N and bit[i + k] < w:
                i += k
                w -= bit[i]
        return i + 1

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

memo = {a: i for i, a in enumerate(sorted(set(A)), 1)}
M = len(memo)

bit = BIT(M)
for b in (memo[a] for a in A):
    s = bit.sum(b - 1)
    if s > 0:
        i = bit.bisect(s)
        bit.add(i, -1)
    bit.add(b, 1)

print(bit.sum(M))

Solution (Python):
class BIT:
    def __init__(self, N):
        self.size = N
        self.tree = [0] * (N + 1)
        self.bisect_K = [1 << k for k in reversed(range(N.bit_length()))]

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

    def bisect(self, w):
        bit, N = self.tree, self.size
        i = 0
        for k in self.bisect_K:
            if i + k <= N and bit[i + k] < w:
                i += k
                w -= bit[i]
        return i + 1

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

memo = {a: i for i, a in enumerate(sorted(set(A)), 1)}
M = len(memo)

bit = BIT(M)
for b in (memo[a] for a in A):
    s = bit.sum(b - 1)
    if s > 0:
        i = bit.bisect(s)
        bit.add(i, -1)
    bit.add(b, 1)

print(bit.sum(M))

Solution (Python):
class BIT:
    def __init__(self, N):
        self.size = N
        self.tree = [0] * (N + 1)
        self.MSB = 1 << (N.bit_length() - 1)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

    def bisect(self, w):
        bit, N = self.tree, self.size
        i = 0
        K = N.bit_length()
        for k in (1 << k for k in reversed(range(K))):
            if i + k <= N and bit[i + k] < w:
                w -= bit[i + k]
                i += k
        return i + 1

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

memo = {a: i for i, a in enumerate(sorted(set(A)), 1)}
M = len(memo)

bit = BIT(M)
for b in (memo[a] for a in A):
    s = bit.sum(b - 1)
    if s > 0:
        i = bit.bisect(s)
        bit.add(i, -1)
    bit.add(b, 1)

print(bit.sum(M))

Solution (Python):
class BIT:
    def __init__(self, N):
        self.size = N
        self.tree = [0] * (N + 1)
        self.MSB = 1 << (N.bit_length() - 1)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

    def bisect(self, w):
        bit, N = self.tree, self.size
        i = 0
        k = self.MSB
        while k > 0:
            if i + k <= N and bit[i + k] < w:
                w -= bit[i + k]
                i += k
            k //= 2
        return i + 1

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

memo = {a: i for i, a in enumerate(sorted(set(A)), 1)}
M = len(memo)

bit = BIT(M)
for b in (memo[a] for a in A):
    s = bit.sum(b - 1)
    if s > 0:
        i = bit.bisect(s)
        bit.add(i, -1)
    bit.add(b, 1)

print(bit.sum(M))

Solution (Python):
class BIT:
    def __init__(self, N):
        self.size = N
        self.tree = [0] * (N + 1)
        self.MSB = 1 << (N.bit_length() - 1)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

    def bisect(self, w):
        bit, N = self.tree, self.size
        i = 0
        k = self.MSB
        while k > 0:
            if i + k <= N and bit[i + k] < w:
                w -= bit[i + k]
                i += k
            k //= 2
        return i + 1

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

memo = {a: i for i, a in enumerate(sorted(set(A)), 1)}
M = len(memo)

bit = BIT(M)
for b in (memo[a] for a in A):
    s = bit.sum(b - 1)
    if s > 0:
        i = bit.bisect(s)
        bit.add(i, -1)
    bit.add(b, 1)

print(bit.sum(M))

Solution (Python):
class BIT:
    def __init__(self, N):
        self.size = N
        self.tree = [0] * (N + 1)
        self.MSB = 1 << (N.bit_length() - 1)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

    def bisect(self, w):
        bit, N = self.tree, self.size
        i = 0
        k = self.MSB
        while k > 0:
            if i + k <= N and bit[i + k] < w:
                w -= bit[i + k]
                i += k
            k //= 2
        return i + 1

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

memo = {a: i for i, a in enumerate(sorted(set(A)), 1)}
B = [memo[a] for a in A]
M = len(memo) + 10

bit = BIT(M)
for b in B:
    s = bit.sum(b - 1)
    if s > 0:
        i = bit.bisect(s)
        bit.add(i, -1)
    bit.add(b, 1)

print(bit.sum(M))

Solution (Python):
class BIT:
    def __init__(self, N):
        self.size = N
        self.tree = [0] * (N + 1)
        self.bisect_k = 1 << (N.bit_length() - 1)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

    def __str__(self):
        return "BIT: [{}]".format(
            ", ".join(str(self.sum(i + 1) - self.sum(i))
                      for i in range(self.size))
        )

    def bisect(self, w):
        bit, N = self.tree, self.size
        i = 0
        k = self.bisect_k
        while k > 0:
            if i + k <= N and bit[i + k] < w:
                w -= bit[i + k]
                i += k
            k //= 2
        return i + 1

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

memo = {a: i for i, a in enumerate(sorted(set(A)), 1)}
B = [memo[a] for a in A]
M = len(memo) + 10

bit = BIT(M)
for b in B:
    s = bit.sum(b - 1)
    if s > 0:
        i = bit.bisect(s)
        bit.add(i, -1)
    bit.add(b, 1)

print(bit.sum(M))

Solution (Python):
class BIT:
    def __init__(self, N):
        self.size = N
        self.tree = [0] * (N + 1)
        self.bisect_k = 1 << (N.bit_length() - 1)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

    def __str__(self):
        return "BIT: [{}]".format(
            ", ".join(str(self.sum(i + 1) - self.sum(i))
                      for i in range(self.size))
        )

    def bisect(self, w):
        bit, N = self.tree, self.size
        i = 0
        k = self.bisect_k
        while k > 0:
            if i + k <= N and bit[i + k] < w:
                w -= bit[i + k]
                i += k
            k //= 2
        return i + 1

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

memo = {a: i for i, a in enumerate(sorted(set(A)), 1)}
B = [memo[a] for a in A]
M = len(memo) + 10

bit = BIT(M)
for b in B:
    s = bit.sum(b - 1)
    if s > 0:
        i = bit.bisect(s)
        bit.add(i, -1)
    bit.add(b, 1)

print(bit.sum(M))

Solution (Python):
class BIT:
    def __init__(self, N):
        self.size = N
        self.tree = [0] * (N + 1)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

    def __str__(self):
        return "BIT: [{}]".format(
            ", ".join(str(self.sum(i + 1) - self.sum(i))
                      for i in range(self.size))
        )

    def bisect(self, w):
        bit, N = self.tree, self.size
        i = 0
        k = 1 << (N.bit_length() - 1)
        while k > 0:
            if i + k <= N and bit[i + k] < w:
                w -= bit[i + k]
                i += k
            k //= 2
        return i + 1

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

memo = {a: i for i, a in enumerate(sorted(set(A)), 1)}
B = [memo[a] for a in A]
M = len(memo) + 10

bit = BIT(M)
for b in B:
    s = bit.sum(b - 1)
    if s > 0:
        i = bit.bisect(s)
        bit.add(i, -1)
    bit.add(b, 1)

print(bit.sum(M))

Solution (Python):
class BIT:
    def __init__(self, N):
        self.size = N
        self.tree = [0] * (N + 1)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

    def __str__(self):
        return "BIT: [{}]".format(
            ", ".join(str(self.sum(i + 1) - self.sum(i))
                      for i in range(self.size))
        )

    def bisect(self, w):
        bit, N = self.tree, self.size
        i = 0
        k = 1 << (N.bit_length() - 1)
        while k > 0:
            if i + k <= N and bit[i + k] < w:
                w -= bit[i + k]
                i += k
            k //= 2
        return i + 1

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

memo = {a: i for i, a in enumerate(sorted(set(A)), 1)}
B = [memo[a] for a in A]
M = len(memo) + 10

bit = BIT(M)
for b in B:
    s = bit.sum(b - 1)
    if s > 0:
        i = bit.bisect(s)
        bit.add(i, -1)
    bit.add(b, 1)

print(bit.sum(M))

Solution (Python):
class BIT:
    def __init__(self, N):
        self.size = N
        self.tree = [0] * (N + 1)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

    def __str__(self):
        return "BIT: [{}]".format(
            ", ".join(str(self.sum(i + 1) - self.sum(i))
                      for i in range(self.size))
        )

    def bisect(self, i):
        l, r = 0, i
        s = self.sum(r)
        if s == 0:
            return 0
        while r - l > 1:
            m = (r + l) // 2
            if self.sum(m) < s:
                l = m
            else:
                r = m
        return l + 1


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

memo = {a: i for i, a in enumerate(sorted(set(A)), 1)}
B = [memo[a] for a in A]
M = len(memo) + 10

bit = BIT(M)
for b in B:
    i = bit.bisect(b - 1)
    if i != 0:
        bit.add(i, -1)
    bit.add(b, 1)

print(bit.sum(M))

Solution (Python):
from bisect import bisect_left as b
n=int(input())
p=[-1]*(n+1)
p[-1]=float("INF")
q=n
for i in range(n):
    x=int(input())
    d=b(p,x)-1
    q=min(q,d)
    p[d]=x
print(n-q)

Solution (Python):
import sys
import bisect

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

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

	return(len(l))

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

main()

Solution (Python):
from bisect import bisect_right
N = int(input())
dp = [float("inf") for _ in range(N+1)]

rows = 0
for _ in range(N):
    c = -float(input())
    i = bisect_right(dp, c)
    if i == rows:
        rows += 1
    dp[i] = c
print(len(list(filter(lambda x:x < float("inf"), dp))))

Solution (Python):
import bisect as b
from collections import deque
n=int(input())
ans=1
clist=deque([int(input())])
for i in range(n-1):
    next=int(input())
    pos=b.bisect_left(clist,next)
    if pos==0:
        clist.appendleft(next)
        ans+=1
    else:
        clist[pos-1]=next
print(ans)

Solution (Python):
from bisect import bisect_right

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

A.reverse()

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

print(len(dp))

Solution (Python):
def se(c, x, h, l):
    if h == l:
        return l
    t = (h+l)//2
    if c[t] <= x:
        a = se(c,x,h,t+1)
    else:
        a = se(c,x,t,l)
    return a
        
    
import numpy as np
n = int(input())
a = [int(input()) for i in range(n)]
c = [a[-1]]
diff = np.diff(a)
tmp = np.sum(diff<=0)
if tmp == len(diff):
    print(len(a))
elif tmp == 0:
    print(1)
else:
    for i in a[::-1][1:]:
        if c[-1] <= i:
            c.append(i)
        else:
            c[se(c,i,len(c),0)] = i
    print(len(c))

Solution (Python):
import sys
import bisect

n = int(input())
a = [int(sys.stdin.readline().rstrip()) for _ in range(n)][::-1]

bottoms = [a[0]]

for i in range(1, n):
    pos = bisect.bisect_right(bottoms, a[i])
    if pos == len(bottoms):
        bottoms.append(a[i])
    else:
        bottoms[pos] = a[i]

print(len(bottoms))

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

Solution (Python):
from bisect import bisect


n = int(input())
seq = []
for i in range(n):
	ele = int(input())
	pos = bisect(seq, -ele)
	if len(seq) <= pos:
		seq.append(-ele)
	else:
		seq[pos] = -ele 
print(len(seq))

Solution (Python):
import bisect
from collections import deque
N = int(input())
S = deque([int(input())])
for _ in range(N-1):
    a = int(input())
    ind = bisect.bisect_right(S,a)
    if S[ind-1]==a:
        ind1 = bisect.bisect_left(S,a)
        if ind1>0 and S[ind1-1]<a:
            S[ind1-1]=a
        else:
            S.appendleft(a)
    elif ind==0:
        S.appendleft(a)
    else:
        S[ind-1]=a

print(len(S))

Solution (Python):
from bisect import bisect

n = int(input())

seq = []
for i in range(n):
	ele = int(input())
	pos = bisect(seq, -ele)
	if len(seq) <= pos:
		seq.append(-ele)
	else:
		seq[pos] = -ele

print(len(seq))

Solution (Python):
from bisect import bisect

n = int(input())

seq = []
for i in range(n):
	ele = int(input())
	pos = bisect(seq, -ele)
	if len(seq) <= pos:
		seq.append(-ele)
	else:
		seq[pos] = -ele

print(len(seq))

Solution (Python):


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

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

print(LIS(a))

Solution (Python):


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

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

print(LIS(a))

Solution (Python):
import bisect

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

colors = []
max_val = -1 * (10 ** 10)
for num in nums:
	if num >= max_val:
		colors.append(num)
		max_val = num
	else:
		idx_r = bisect.bisect_right(colors, num)
		colors[idx_r] = num
		max_val = min(colors[-1], max_val)

print(len(colors))

Solution (Python):
import bisect

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

colors = []
max_val = -1 * (10 ** 10)
for num in nums:
	if num >= max_val:
		colors.append(num)
		max_val = num
	else:
		idx_r = bisect.bisect_right(colors, num)
		colors[idx_r] = num
		max_val = min(colors[-1], max_val)

print(len(colors))

Solution (Python):
import bisect

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

colors.append(arr[-1])
cnum = len(colors)
for a in arr[-2::-1]:
  i = bisect.bisect_right(colors, a)
  if i < cnum:
    colors[i] = a
  else:
    colors.append(a)
    cnum += 1

print(cnum)

Solution (Python):











import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,log 
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf=float('inf')
mod = 10**9+7
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N = I()
    A = LIN(N)[::-1] 
    LIS = [A[0]] 
    for a in A[1:]:
        if LIS[-1] <= a:
            LIS.append(a)
        else:
            update_index = bisect_right(LIS,a)
            LIS[update_index] = a
    print(len(LIS))





if __name__ == '__main__':
    main()

Solution (Python):
import bisect

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

ans = [-1] * n
for b in a:
    ans[bisect.bisect(ans, b-1) - 1] = b

print(n - bisect.bisect(ans, -1))

Solution (Python):

import sys
input = sys.stdin.readline  

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

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

    print(len(dp))

if __name__ == '__main__':
    main()