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):
def JOI14_B():
    N = I()
    A = [I()for _ in range(N)]
    A.extend(A)
    dp = [[0]*(N*2+1) for _ in range(N*2+1)]

    for j in range(N):
        for i in range(N*2-j):
            if (N-j)%2==1:
                dp[i][i+j] = max(dp[i+1][i+j]+A[i],dp[i][i+j-1]+A[i+j])
            else:
                if A[i]>A[i+j]:
                    dp[i][i+j] = dp[i+1][i+j]
                else:
                    dp[i][i+j] = dp[i][i+j-1]
    ans = 0
    for i in range(N):
        ans = max(ans,dp[i][i+N-1])
    print(ans)
    
    return

def square869120Contest1_G():
    def held_karp(dists,TL):
        
        """
        Implementation of Held-Karp, an algorithm that solves the Traveling
        Salesman Problem using dynamic programming with memoization.
        Parameters:
            dists: distance matrix
        Returns:
            A tuple, (cost, path).
        """
        n = len(dists)

        
        
        
        C = {}
        dp = defaultdict(int)

        
        for k in range(1, n):
            C[(1 << k, k)] = (dists[0][k], 0)
            dp[(1 << k, k)] = 1

        
        
        for subset_size in range(2, n):
            for subset in itertools.combinations(range(1, n), subset_size):
                
                bits = 0
                for bit in subset:
                    bits |= 1 << bit
                shortest_length = inf
                
                for k in subset:
                    prev = bits & ~(1 << k)

                    res = []
                    for m in subset:
                        if not (prev, m) in C:
                            continue
                        if m == 0 or m == k:
                            continue
                        if C[(prev, m)][0] + dists[m][k]>TL[m][k]:
                            continue
                        res.append((C[(prev, m)][0] + dists[m][k], m))
                        if shortest_length>C[(prev, m)][0] + dists[m][k]:
                            shortest_length = C[(prev, m)][0] + dists[m][k]
                    if not res:
                        continue
                    C[(bits, k)] = min(res)
                    for d,m in res:
                        if shortest_length!=d:
                            continue
                        dp[(bits, k)] += dp[(prev,m)]

        
        bits = (2 ** n - 1) - 1

        
        res = []
        shortest_length = inf
        for k in range(1, n):
            if not (bits, k) in C:
                continue
            if C[(bits, k)][0] + dists[k][0] > TL[k][0]:
                continue
            res.append((C[(bits, k)][0] + dists[k][0], k))
            if shortest_length > C[(bits, k)][0] + dists[k][0]:
                shortest_length = C[(bits, k)][0] + dists[k][0]
        if not res:
            return False
        opt, parent = min(res)
        way = 0
        for d, k in res:
            if not (bits, k) in C:
                continue
            if C[(bits, k)][0] + dists[k][0] > TL[k][0]:
                continue
            if shortest_length < d:
                continue
            way += dp[(bits,k)]

        
        path = []
        for i in range(n - 1):
            path.append(parent)
            new_bits = bits & ~(1 << parent)
            _, parent = C[(bits, parent)]
            bits = new_bits

        
        path.append(0)

        return shortest_length, list(reversed(path)), way

    N, M = LI()
    dist = [[inf]*N for _ in range(N)]
    TL = [[0]*N for _ in range(N)]
    for _ in range(M):
        s, t, d, time = LI()
        s -= 1; t -= 1
        dist[s][t] = dist[t][s] = d
        TL[s][t] = TL[t][s] = time
    ans = held_karp(dist,TL)
    if (not ans) or ans[2]==0:
        print("IMPOSSIBLE")
        return
    print(ans[0],ans[2])
    return

def JOI13_D():
    def solve(yday,leader,next):
        a = [0]*3
        for i in range(3):
            if next&(1<<i)==(1<<i):
                a[i] = 1
        rep = 0
        if a[leader]==0:
            return rep
        for i in range(3):
            if yday&(1<<i)==(1<<i):
                if a[i]==1:
                    rep = 1
        return rep
    N = I()
    S = SI()
    member = {"J":0,"O":1,"I":2}
    dp = [[0]*8 for _ in range(N+1)]
    dp[0][1] = 1
    for i in range(N):
        leader = member[S[i]]
        for j in range(8):
            for k in range(8):
                dp[i+1][j] += (dp[i][k]*solve(k,leader,j))
    ans = sum(dp[-1])%10007
    
    print(ans)
    return

def JOI16_D():
    N, M = LI()
    A = [(I()-1)for _ in range(N)]
    imos = [[0] * (N + 1) for _ in range(M)]
    for i in range(M):
        for j in range(N):
            imos[i][j + 1] += imos[i][j] + (A[j] != i)
    cnt = Counter(A)
    dp = [10 ** 9] * (1 << M)
    num = [None] * (1 << M)
    dp[0] = 0
    num[0] = 0
    for b in range(1 << M):
        for i in range(M):
            if b & (1 << i):
                continue
            nb = b | (1 << i)
            if num[nb] is None:
                num[nb] = num[b] + cnt[i]
            l = num[b]
            r = l + cnt[i]
            d = imos[i][r] - imos[i][l]
            dp[nb] = min(dp[nb], dp[b] + d)

    print(dp[-1])
    return

def ABC6_D():
    N = I()
    C = [I() for _ in range(N)]
    LIS = [C[0]]
    for i in range(N):
        if C[i] > LIS[-1]:
            LIS.append(C[i])
        else:
            LIS[bisect.bisect_left(LIS, C[i])] = C[i]
    print(N - len(LIS))
    return

def ABC134_E():
    N = I()
    A = [I()for _ in range(N)]
    que = deque()
    que.append(A[0])
    L = 1
    for i in range(1,N):
        cur = bisect.bisect_left(que,A[i])
        
        if cur==0:
            que.appendleft(A[i])
            L += 1
        else:
            que[cur-1] = A[i]

    
    ans = len(que)
    print(ans)

    return

def JOI7_F():
    n, k = LI()
    for _ in range(k):
        A = LI()

    return

def square869120Contest1_E():
    N, Q = LI()
    A = LI()
    C = LI()
    C.append(1)
    L = [0]*N
    for i in range(1,N):
        L[i] = pow(A[i-1],A[i],mod) + L[i-1]
    
    ans = 0
    now = 0
    for i in range(Q+1):
        next = C[i]-1
        cur = abs(L[next]-L[now])
        ans += cur
        ans %= mod
        now = next
        
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math,random
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

if __name__ == '__main__':
    ABC134_E()
"""

"""

Solution (Python):
import sys
from bisect import bisect_right as br
input = sys.stdin.readline
N = int(input())
a = []
for _ in range(N): a.append(int(input()))
lis = [float("inf") for _ in range(N)]
reva = a[: : -1]

for i in range(N):
  j = br(lis, reva[i])
  lis[j] = reva[i]

res = N
for i in range(N):
  if lis[i] == float("inf"):
    res = i
    break
print(res)

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

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

col = [A.pop()]
col = deque(col)

while A:
    a = A.pop()
    if a <= col[0]:
        col.appendleft(a)
    else:
        x = bisect.bisect_left(col, a)
        col[x - 1] = a

ans = len(col)
print(ans)

Solution (Python):

import sys
from collections import deque
from bisect import bisect_left

def solve(N: int, A: "List[int]"):
    deq = deque([-1])

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

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    A = [int(next(tokens)) for _ in range(N)]  
    solve(N, A)

if __name__ == '__main__':
    main()

Solution (Python):

import sys
from collections import deque
from bisect import bisect_left

def solve(N: int, A: "List[int]"):
    deq = deque([-1])

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

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    A = [int(next(tokens)) for _ in range(N)]  
    solve(N, A)

if __name__ == '__main__':
    main()

Solution (Python):
from bisect import bisect_right

def I(): return int(input())
def MI(): return map(int, input().split())
def LMI(): return list(map(int, input().split()))
MOD = 10 ** 9 + 7

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



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

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

sys.setrecursionlimit(10000)

N = int(input())
import bisect

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

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

def main():
    N = int(input())
    use = deque([10**9+1])
    for _ in range(N):
        num = int(input())
        index = bisect.bisect_left(use,num)
        if index == 0:
            use.appendleft(num)
        else:
            use[index-1] = num
    
    print(len(use)-1)
    
if __name__ == "__main__":
    main()

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

def main():
    N = int(input())
    use = deque([int(input())])
    for _ in range(N-1):
        num = int(input())
        index = bisect.bisect_left(use,num)
        if index == 0:
            use.appendleft(num)
        else:
            use[index-1] = num
    
    print(len(use))
    
if __name__ == "__main__":
    main()

Solution (Python):
from bisect import bisect
def main():
    N,*A=map(int, open(0).read().split())
    B=[]
    for a in A:
        x=bisect(B,-a)
        if x>=len(B):
            B.append(-a)
        else:
            B[x]=-a
    print(len(B))

if __name__ == "__main__":
    main()

Solution (Python):







from bisect import bisect_right

inf = 10 ** 9 + 1

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

t = [inf]
for x in reversed(a):
    if t[-1] <= x:
        t.append(x)
    else:
        insert_pos = bisect_right(t, x)
        t[insert_pos] = x

ret = len(t)

print(ret)

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

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

q = deque([-1])
for x in a:
    insert_pos = bisect_left(q, x) - 1
    
    
    if insert_pos == -1:
        q.appendleft(x)
    else:
        q[insert_pos] = x

ret = len(q)

print(ret)

Solution (Python):

from collections import deque
import bisect
n = int(input())
now = deque()
for _ in range(n):
  tmp = int(input())
  b = bisect.bisect_left(now,tmp)
  if b != 0:
    now[b-1] = tmp
  else:
    now.appendleft(tmp)
print(len(now))

Solution (Python):

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

def main():
  n = I()
  a = [I() for _ in range(n)]
  dp = [inf]*n
  for i in range(n):
    r = br(dp,-a[i])
    dp[r] = -a[i]
  print(n-dp.count(inf))
  return

if __name__ == '__main__':
  main()

Solution (Python):
from bisect import bisect_left
from collections import deque
N = int(input())
a = int(input())
ls = deque([a])
for i in range(N-1):
  c = int(input())
  ind = bisect_left(ls,c)
  if ind==0:
    ls.appendleft(c)
    continue
  ls[ind-1] = c
print(len(ls))

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

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

Solution (Python):
import bisect

N = int(input())
H = []
for _ in range(N):
    a = int(input())
    ind = bisect.bisect_right(H, -a)
    if ind == len(H):
        H.append(-a)
    else:
        H[ind] = -a
print(len(H))

Solution (Python):
import bisect

def main():
    n = int(input())
    buf = []
    a = [None] * n
    for i in range(n):
        a[i] = int(input())
    for i in reversed(a):
        index = bisect.bisect_right(buf, i)
        if index < len(buf) and buf[index] > i:
            buf[index] = i
        else:
            buf.append(i)
    print(len(buf))

if __name__ == "__main__":
    main()

Solution (Python):
import sys
from bisect import bisect_right as bi_r

inf = float('inf')

n, *A = map(int, sys.stdin.read().split())

def main():
    res = [inf] * n
    for a in A[::-1]:
        i = bi_r(res, a)
        res[i] = a

    for i in range(n):
        if res[i] == inf:
            return i
    return n
    
if __name__ == '__main__':
    ans = main()
    print(ans)

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

ans=1
data=deque([A[0]])
for i in range(1,N):
    a=A[i]
    b=bisect_left(data,a)
    if b==0:
        data.appendleft(a)
        ans+=1
    else:
        data[b-1]=a

print(ans)

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

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

d = []
for i in range(N):
    p = bisect.bisect_right(d, A[i])
    if p==len(d):
        d.append(A[i])
    else:
        d[p] = A[i]
ans = len(d)
print(ans)

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

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

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

Solution (Python):
from collections import deque
import bisect

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

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

Solution (Python):
import sys
import bisect

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
INF = 10 ** 10
dp = [INF] * N

for _ in range(N):
    a = 10 ** 9 - ir()
    i = bisect.bisect_right(dp, a)
    dp[i] = a

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

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

N = int(input())
d = deque([])
l = [int(input()) for _ in range(N)]

d.append(l[0])

for i in l[1:]:
    v = bisect_left(d, i)
    if v == 0:
        d.appendleft(i)
    else:
        d[v-1] = i

print(len(d))

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

stack = []

def bisect(li, i):
    if len(li)==0:
        li.append(i)
        return
    ok = len(li)
    ng = -1
    while abs(ok-ng)>1:
        tmp = (ok+ng)//2
        if li[tmp]<i:
            ok = tmp
        else:
            ng = tmp
    if ok < len(li):
        li[ok] = i
    else:
        li.append(i)

for i in a:
    bisect(stack, i)
print(len(stack))

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

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

print(len(B))

Solution (Python):
from bisect import bisect_right

N = int(input())
A = [int(input()) for _ in range(N)]
INF = float('inf')

dp = [-A[0]]
cnt = 1
for i in range(1, N):
    a = -A[i]
    idx = bisect_right(dp, a)
    if idx == cnt:
        dp.append(a)
        cnt += 1
    else:
        dp[idx] = a

print(cnt)

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

X = deque([])

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


print(len(X))

Solution (Python):
from bisect import bisect_right
N = int(input())
A = [int(input()) for i in range(N)]
A = [-a for a in A]

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


print(len(X))

Solution (Python):

import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

n=int(input())
A=[int(input()) for i in range(n)]
data=collections.deque()
for i, ai in enumerate(A):
    k=bisect.bisect_left(data,ai)
    if k==0:
        data.appendleft(ai)
    else:
        data[k-1]=ai
print(len(data))

Solution (Python):

import bisect


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

  tail = []
  len_tail = 0
  for ai in a:
    idx = bisect.bisect_right(tail, -ai, lo=0, hi=len_tail) 
    if idx == len_tail:
      tail.append(-ai)
      len_tail += 1
    else:
      tail[idx] = - ai

  print(len_tail )


if __name__ == "__main__":
  main()

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

Solution (Python):
import bisect


class Deque:
    def __init__(self, src_arr=[], max_size=300000):
        self.N = max(max_size, len(src_arr)) + 1
        self.buf = list(src_arr) + [None] * (self.N - len(src_arr))
        self.head = 0
        self.tail = len(src_arr)

    def __index(self, i):
        l = len(self)
        if not -l <= i < l: raise IndexError('index out of range: ' + str(i))
        if i < 0:
            i += l
        return (self.head + i) % self.N

    def __extend(self):
        ex = self.N - 1
        self.buf[self.tail + 1: self.tail + 1] = [None] * ex
        self.N = len(self.buf)
        if self.head > 0:
            self.head += ex

    def is_full(self):
        return len(self) >= self.N - 1

    def is_empty(self):
        return len(self) == 0

    def append(self, x):
        if self.is_full(): self.__extend()
        self.buf[self.tail] = x
        self.tail += 1
        self.tail %= self.N

    def appendleft(self, x):
        if self.is_full(): self.__extend()
        self.buf[(self.head - 1) % self.N] = x
        self.head -= 1
        self.head %= self.N

    def pop(self):
        if self.is_empty(): raise IndexError('pop() when buffer is empty')
        ret = self.buf[(self.tail - 1) % self.N]
        self.tail -= 1
        self.tail %= self.N
        return ret

    def popleft(self):
        if self.is_empty(): raise IndexError('popleft() when buffer is empty')
        ret = self.buf[self.head]
        self.head += 1
        self.head %= self.N
        return ret

    def __len__(self):
        return (self.tail - self.head) % self.N

    def __getitem__(self, key):
        return self.buf[self.__index(key)]

    def __setitem__(self, key, value):
        self.buf[self.__index(key)] = value

    def __str__(self):
        return 'Deque({0})'.format(str(list(self)))


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

x = Deque()

for i, a in enumerate(A):
    if i == 0:
        x.append(a)
    else:
        r = bisect.bisect_left(x, a)
        if r == 0:
            x.appendleft(a)
        else:
            x[r - 1] = a

print(len(x))

Solution (Python):
import bisect
import  collections

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

x = collections.deque()

for i, a in enumerate(A):
    if i == 0:
        x.append(a)
    else:
        r = bisect.bisect_left(x, a)
        if r == 0:
            x.appendleft(a)
        else:
            x[r - 1] = a

print(len(x))

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

def main():
    N = int(input())
    A = [int(input()) for _ in range(N)]
    d = deque([])
    d.append(A[0])
    for i in range(1,N):
        p = bisect_left(d, A[i])
        if p == 0:
            d.appendleft(A[i])
        else:
            d[p-1] = A[i]

    print(len(d))


if __name__ == "__main__":
    main()

Solution (Python):
import bisect
n = int(input())
a = [int(input()) for _ in range(n)]
dp = [float('inf')]*n
for i in range(n):
  c = a[n-i-1]
  b = bisect.bisect_right(dp,c)
  if dp[b] > c:
    dp[b] = c
print(bisect.bisect_right(dp,10**9+1))

Solution (Python):
import bisect

N = int(input())

A = []

for i in range(N):

    a = int(input())
    A.append(a)

A.reverse()

seq = [float("-inf")]

for i in A:

    ind = bisect.bisect_right(seq,i)

    if ind == len(seq):
        seq.append(i)
    else:
        seq[ind] = i

print (len(seq)-1)

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

from collections import deque
import bisect

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

print(len(d))

Solution (Python):
import bisect
def main():
    N = int(input())
    A = []
    c = 1
    l = []
    for _ in range(N):
        a = int(input())
        A.append(a)
    l.append(A[-1])
    for j in reversed(A[:-1]):
        i = bisect.bisect_right(l, j)
        if i == len(l):
            l.append(j)
        else:
            l[i] = j
    print(len(l))
main()

Solution (Python):
import bisect
def bisect_rev(a, x):
    lo = 0
    hi = len(a)
    while lo < hi:
        mid = (lo + hi) // 2
        if x > a[mid]:
            hi = mid
        else:
            lo = mid + 1
    return lo

def main():
    N = int(input())
    A = [int(input()) for _ in range(N)]
    t = []
    for a in A:
        k = bisect_rev(t, a)
        if k == len(t):
            t.append(a)
        else:
            t[k] = a
    return len(t)

print(main())

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

b = [a[-1]]
for i in range(n - 2, -1, -1):
    if b[-1] <= a[i]:
        b.append(a[i])
    else:
        b[bisect.bisect_right(b, a[i])] = a[i]

print(len(b))

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


def LIS(L):
    INF = float('inf')
    DP = [INF]*(N+1)

    def bisect(v):
        if v<DP[0]:
            return 0
        l = 0
        r = N
        while r-l>1:
            if v<DP[(l+r)//2]:
            
                r = (l+r)//2
            else:
                l = (l+r)//2
        return r
    
    for v in L:
        DP[bisect(v)] = v
    return DP

DP = LIS(A)
count = 0
for i in range(N):
    if DP[i]<10**10:
        count+=1
    else:
        break
print(count)

Solution (Python):
import bisect
from collections import deque
N=int(input())
a=deque([int(input())])
for _ in range(N-1):
  num=int(input())
  if num<=a[0]:
    a.appendleft(num)
  else:
    a[bisect.bisect_left(a, num)-1]=num
print(len(a))

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

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

c, ans = deque(), 0

for i in range(n):   
    t = bisect_right(c, a[i]-1) - 1
    if t < 0: c.appendleft(a[i])
    else: c[t] = a[i]

print(len(c))

Solution (Python):
import bisect

n = int(input())


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

ans = [A[0]]
for a in A[1:]:
  
  if a >= ans[-1]:
    ans.append(a)
  else:
    pos = bisect.bisect_right(ans, a) 
    ans[pos] = a 
print(len(ans))

Solution (Python):
import bisect

n = int(input())


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

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

Solution (Python):

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

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
N = int(input())
seq = [-int(input()) for i in range(N)] 
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]
print(len(LIS))

Solution (Python):
import sys
input = sys.stdin.readline
import bisect
N = int(input())
a = [-int(input()) for i in range(N)]
ls = []
res = 0
for elem in a:
    idx = bisect.bisect_right(ls,elem)
    if idx == res:
        ls.append(elem)
        res += 1
    else:
        ls[idx] = elem
print(res)

Solution (Python):

from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect
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():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
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 solve():
    n = I()
    a = IR(n)
    dp = [float("inf")]*n
    m = max(a)
    for i in a:
        j = m-i
        ind = bisect.bisect_right(dp,j)
        dp[ind] = j
    print(len(dp)-dp.count(float("inf")))
    return


if __name__ == "__main__":
    solve()

Solution (Python):
import sys

read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs = sys.stdin.buffer.readlines







import bisect
from collections import deque


def main():
	n=int(input())
	A=[int(input()) for _ in range(n)]
	
	Q=deque([A[0]])
	
	for i in range(1,n):
		if A[i]<=Q[0]:
			Q.appendleft(A[i])

		else:
			ix=bisect.bisect_left(Q,A[i])
			Q[ix-1]=A[i]
	
	print(len(Q))
	
	
	
	
	



if __name__ == "__main__":
	main()

Solution (Python):
import sys

read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs = sys.stdin.buffer.readlines







import bisect
from collections import deque


def main():
	n=int(input())
	A=[int(input()) for _ in range(n)]
	
	Q=deque([A[0]])
	
	for i in range(1,n):
		if A[i]<=Q[0]:
			Q.appendleft(A[i])

		else:
			ix=bisect.bisect_left(Q,A[i])
			Q[ix-1]=A[i]
	
	print(len(Q))
	
	
	
	
	



if __name__ == "__main__":
	main()

Solution (Python):
import bisect

n = int(input())

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

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

for x in a[1:]:
  i = bisect.bisect_left(ary, x)
  if i == 0:
    ary[0:0] = [x]
  else:
    ary[i-1:i] = [x]
       
print(len(ary))

Solution (Python):
import bisect
n = int(input())
A = [int(input()) for _ in range(n)]
L = [-1]*n
count = 0
for i in A:
  t = bisect.bisect_left(L, i) - 1
  if L[t] == -1:
    count += 1
  L[t] = i
print(count)

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



d=[]
d.append(int(input()))
for i in range(n-1):
  a=int(input())
  ok=len(d)
  ng=-1
  while abs(ok-ng)>1:
    mid=abs(ok+ng)//2
    if d[mid]<a:
      ok=mid
    else:
      ng=mid
  if ok==len(d):
    d.append(a)
  else:
    d[ok]=a
print(len(d))

Solution (Python):



import bisect

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

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

for i in range(1,N):
    index=bisect.bisect_right(b,A[i])
    if index==len(b):
        b.append(A[i])
    else:
        b[index]=A[i]
print(len(b))

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




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


def bi_s(n):
    if b[-1]>=n:
        return -1
    if n>b[0]:
        return 0
    
    ceil=0
    floor=len(b)-1
    med=1
    while abs(floor-ceil)>1:
        med=(ceil+floor)//2
        if n>b[med]:
            floor=med
        else:
            ceil=med
    return floor

for i in range(1,N):
    index=bi_s(A[i])
    if index==-1:
        b.append(A[i])
    else:
        b[index]=A[i]
print(len(b))

Solution (Python):
import sys
from collections import deque
import time
import bisect
def input():
    return sys.stdin.readline()[:-1]
n=int(input())
a=[int(input()) for i in range(n)]

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

print(len(ans))

Solution (Python):
import sys
import bisect
input = sys.stdin.readline
n = int(input())
a = [int(input()) for i in range(n)]
ans = 0
color = [a[n-1]]
for i in range(n-2,-1,-1):
    if a[i]>=color[-1]:
        color.append(a[i])
    else:
        x = bisect.bisect_right(color,a[i])
        color[x] = a[i]
print(len(color))

Solution (Python):
import sys
import bisect
input = sys.stdin.readline
n = int(input())
a = [int(input()) for i in range(n)]
ans = 0
color = [a[n-1]]
for i in range(n-2,-1,-1):
    if a[i]>=color[-1]:
        color.append(a[i])
    else:
        x = bisect.bisect_right(color,a[i])
        color[x] = a[i]
print(len(color))

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

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

Solution (Python):
import bisect
from collections import deque

N = int(input())
A = deque([-1])

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

print(len(A))

Solution (Python):
import bisect

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