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):
N=int(input())
A=[int(input()) for i in range(N)]
from bisect import bisect_left
from collections import deque
l=deque()
for a in A:
    i=bisect_left(l,a)
    if i==0:
        l.appendleft(a)
    else:
        l[i-1]=a
print(len(l))

Solution (Python):
from bisect import bisect_right as br
N = int(input())
X = [-1] * N
for _ in range(N):
    a = int(input())
    i = br(X, a-1) - 1
    X[i] = a

print(N - X.count(-1))

Solution (Python):
import sys
from bisect import bisect

n = int(input())
aaa = list(map(int, sys.stdin.readlines()))

dp = [1]
for a in aaa:
    a *= -1
    i = bisect(dp, a)
    if i < len(dp):
        dp[i] = a
    else:
        dp.append(a)
print(len(dp))

Solution (Python):
from collections import *
import sys
inp = raw_input

def err(s):
    sys.stderr.write('{}\n'.format(s))

def ni():
    return int(inp())

def nl():
    return [int(_) for _ in inp().split()]

def lis(X):
    N = len(X)
    P = [0]*N
    M = [0]*(N+1)
    L = 0
    for i in range(N):
        lo, hi = 1, L + 1
        while lo < hi:
            mid = (lo + hi) >> 1
            if X[M[mid]] >= X[i]:
                lo = mid + 1
            else:
                hi = mid
        newL = lo
        P[i] = M[newL - 1]
        M[newL] = i
        L = max(L, newL)
    S = [0]*L
    k = M[L]
    for i in range(L-1, -1, -1):
        S[i] = X[k]
        k = P[k]
    return S

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

print(len(lis(A)))

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

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



dp = [INF] * (N+1) 

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

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