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
input = sys.stdin.readline

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    inf=10**10



    
    from bisect import bisect_left, bisect_right, insort_right
    class SquareSkipList:
        
        
        
        def __init__(self, values=None, sorted_=False, square=1000, seed=42):
            
            
            
            
            
            
            self.cnt=0
            inf = float("inf")
            self.square = square
            if values is None:
                self.rand_y = seed
                self.layer1 = [inf]
                self.layer0 = [[]]
            else:
                self.layer1 = layer1 = []
                self.layer0 = layer0 = []
                if not sorted_:
                    values.sort()
                y = seed
                l0 = []
                for v in values:
                    y ^= (y & 0x7ffff) << 13
                    y ^= y >> 17
                    y ^= (y & 0x7ffffff) << 5
                    if y % square == 0:
                        layer0.append(l0)
                        l0 = []
                        layer1.append(v)
                    else:
                        l0.append(v)
                layer1.append(inf)
                layer0.append(l0)
                self.rand_y = y

        def add(self, x):  
            
            y = self.rand_y
            y ^= (y & 0x7ffff) << 13
            y ^= y >> 17
            y ^= (y & 0x7ffffff) << 5
            self.rand_y = y

            if y % self.square == 0:
                layer1, layer0 = self.layer1, self.layer0
                idx1 = bisect_right(layer1, x)
                layer1.insert(idx1, x)
                layer0_idx1 = layer0[idx1]
                idx0 = bisect_right(layer0_idx1, x)
                layer0.insert(idx1+1, layer0_idx1[idx0:])  
                del layer0_idx1[idx0:]
            else:
                idx1 = bisect_right(self.layer1, x)
                insort_right(self.layer0[idx1], x)
                
            self.cnt+=1

        def remove(self, x):  
            
            idx1 = bisect_left(self.layer1, x)
            layer0_idx1 = self.layer0[idx1]
            idx0 = bisect_left(layer0_idx1, x)
            if idx0 == len(layer0_idx1):
                del self.layer1[idx1]
                self.layer0[idx1] += self.layer0.pop(idx1+1)
            else:
                del layer0_idx1[idx0]
                
            self.cnt-=1

        def search_higher_equal(self, x):  
            idx1 = bisect_left(self.layer1, x)
            layer0_idx1 = self.layer0[idx1]
            idx0 = bisect_left(layer0_idx1, x)
            if idx0 == len(layer0_idx1):
                return self.layer1[idx1]
            return layer0_idx1[idx0]

        def search_higher(self, x):  
            idx1 = bisect_right(self.layer1, x)
            layer0_idx1 = self.layer0[idx1]
            idx0 = bisect_right(layer0_idx1, x)
            if idx0 == len(layer0_idx1):
                return self.layer1[idx1]
            return layer0_idx1[idx0]

        def search_lower(self, x):  
            
            idx1 = bisect_left(self.layer1, x)
            layer0_idx1 = self.layer0[idx1]
            idx0 = bisect_left(layer0_idx1, x)
            if idx0 == 0:  
                return self.layer1[idx1-1]
            return layer0_idx1[idx0-1]

        def pop(self, idx):
            
            
            
            layer0 = self.layer0
            s = -1
            for i, l0 in enumerate(layer0):
                s += len(l0) + 1
                if s >= idx:
                    break
            if s==idx:
                layer0[i] += layer0.pop(i+1)
                return self.layer1.pop(i)
            else:
                return layer0[i].pop(idx-s)

        def print(self):
            print(self.layer1)
            print(self.layer0)
            
        def len(self):
            return self.cnt

    





        

            
    N=I()
    A=[0]*N
    
    for i in range(N):
        A[i]=I()
        
    ssl = SquareSkipList(square=2000)
    ssl.add(-1)
    
    for i in range(N):
        a=A[i]
        m=ssl.search_lower(a)
        if m==-1:
            ssl.add(a)
        else:
            ssl.remove(m)
            ssl.add(a)
            
    print(ssl.len()-1)
    



main()

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    inf=10**10


    
    from bisect import bisect_left, bisect_right, insort_right
    class SquareSkipList:
        
        
        
        def __init__(self, values=None, sorted_=False, square=1000, seed=42):
            
            
            
            
            
            
            inf = float("inf")
            self.square = square
            if values is None:
                self.rand_y = seed
                self.layer1 = [inf]
                self.layer0 = [[]]
            else:
                self.layer1 = layer1 = []
                self.layer0 = layer0 = []
                if not sorted_:
                    values.sort()
                y = seed
                l0 = []
                for v in values:
                    y ^= (y & 0x7ffff) << 13
                    y ^= y >> 17
                    y ^= (y & 0x7ffffff) << 5
                    if y % square == 0:
                        layer0.append(l0)
                        l0 = []
                        layer1.append(v)
                    else:
                        l0.append(v)
                layer1.append(inf)
                layer0.append(l0)
                self.rand_y = y

        def add(self, x):  
            
            y = self.rand_y
            y ^= (y & 0x7ffff) << 13
            y ^= y >> 17
            y ^= (y & 0x7ffffff) << 5
            self.rand_y = y

            if y % self.square == 0:
                layer1, layer0 = self.layer1, self.layer0
                idx1 = bisect_right(layer1, x)
                layer1.insert(idx1, x)
                layer0_idx1 = layer0[idx1]
                idx0 = bisect_right(layer0_idx1, x)
                layer0.insert(idx1+1, layer0_idx1[idx0:])  
                del layer0_idx1[idx0:]
            else:
                idx1 = bisect_right(self.layer1, x)
                insort_right(self.layer0[idx1], x)

        def remove(self, x):  
            
            idx1 = bisect_left(self.layer1, x)
            layer0_idx1 = self.layer0[idx1]
            idx0 = bisect_left(layer0_idx1, x)
            if idx0 == len(layer0_idx1):
                del self.layer1[idx1]
                self.layer0[idx1] += self.layer0.pop(idx1+1)
            else:
                del layer0_idx1[idx0]

        def search_higher_equal(self, x):  
            idx1 = bisect_left(self.layer1, x)
            layer0_idx1 = self.layer0[idx1]
            idx0 = bisect_left(layer0_idx1, x)
            if idx0 == len(layer0_idx1):
                return self.layer1[idx1]
            return layer0_idx1[idx0]

        def search_higher(self, x):  
            idx1 = bisect_right(self.layer1, x)
            layer0_idx1 = self.layer0[idx1]
            idx0 = bisect_right(layer0_idx1, x)
            if idx0 == len(layer0_idx1):
                return self.layer1[idx1]
            return layer0_idx1[idx0]

        def search_lower(self, x):  
            
            idx1 = bisect_left(self.layer1, x)
            layer0_idx1 = self.layer0[idx1]
            idx0 = bisect_left(layer0_idx1, x)
            if idx0 == 0:  
                return self.layer1[idx1-1]
            return layer0_idx1[idx0-1]

        def pop(self, idx):
            
            
            
            layer0 = self.layer0
            s = -1
            for i, l0 in enumerate(layer0):
                s += len(l0) + 1
                if s >= idx:
                    break
            if s==idx:
                layer0[i] += layer0.pop(i+1)
                return self.layer1.pop(i)
            else:
                return layer0[i].pop(idx-s)

        def print(self):
            print(self.layer1)
            print(self.layer0)
            
        def len(self):
            cnt=0
            for l in self.layer0:
                cnt+=len(l)
            cnt+=len(self.layer1)-1
            return cnt

    



        

            
    N=I()
    A=[0]*N
    
    for i in range(N):
        A[i]=I()
        
    ssl = SquareSkipList(square=2000)
    ssl.add(-1)
    
    for i in range(N):
        a=A[i]
        m=ssl.search_lower(a)
        if m==-1:
            ssl.add(a)
        else:
            ssl.remove(m)
            ssl.add(a)
            
    print(ssl.len()-1)
    



main()

Solution (Python):
import bisect

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

B = [A[-1]]
del A[-1]
for a in reversed(A):
    if B[-1] <= a:
        B.append(a)
    else:
        B[bisect.bisect_right(B,a)] = a
    



print(len(B))

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

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

    print(len(ans))



if __name__ == "__main__":
    main()

Solution (Python):
import sys
def input(): return sys.stdin.readline().rstrip()
import bisect
def make_LIS(L):
    LIS=[L[0]]
    for i in range(1,len(L)):
        if L[i]>=LIS[-1]:
            LIS.append(L[i])
        else:
            LIS[bisect.bisect_right(LIS,L[i])]=L[i]
    return len(LIS)
def main():
    n=int(input())
    A=[int(input())for _ in range(n)]
    print(make_LIS(A[::-1]))

if __name__=='__main__':
    main()

Solution (Python):
import sys
def input(): return sys.stdin.readline().rstrip()
import bisect
def make_LIS(L):
    LIS=[L[0]]
    for i in range(1,len(L)):
        if L[i]>=LIS[-1]:
            LIS.append(L[i])
        else:
            LIS[bisect.bisect_right(LIS,L[i])]=L[i]
    return len(LIS)
def main():
    n=int(input())
    A=[int(input())for _ in range(n)]
    print(make_LIS(A[::-1]))

if __name__=='__main__':
    main()

Solution (Python):
from sys import stdin
import bisect
def main():
    
    readline=stdin.readline
    n=int(readline())
    a=[int(readline()) for _ in range(n)]

    li=[]
    for i in range(n):
        if i==0:
            li.append(a[i])
        else:
            l=-1
            r=len(li)
            while l<r-1:
                m=(l+r)//2
                if li[m]>=a[i]:
                    l=m
                else:
                    r=m
            if r==len(li):
                li.append(a[i])
            else:
                li[r]=a[i]

    print(len(li))
    
if __name__=="__main__":
    main()

Solution (Python):
import bisect
from collections import deque
N = int(input())
my_max = deque([10 ** 9 + 1])
prev = -1
ans = 0
for _ in range(N):
    a = int(input())
    x = bisect.bisect_left(my_max, a) 
    if x == 0: 
        my_max.appendleft(a)
        ans += 1
    else:
        my_max[x - 1] = a 
print(ans)

Solution (Python):
N = int(input())
As = [int(input()) for _ in range(N)]
from bisect import bisect_right
from collections import deque

def LIS(L):
    dp = deque([L[0]])
    length = len(L)
    for i in range(1, length):
        a = L[i]
        if a >= dp[-1]:
            dp.append(a)
        else:
            dp[bisect_right(dp, a)] = a
    return dp

print(len(LIS(As[::-1])))

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

import bisect
from collections import deque

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

print(len(lis))

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

import bisect
from collections import deque

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

print(len(lis))

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

import bisect
from collections import deque

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

print(len(lis))

Solution (Python):
import bisect
from collections import deque

n = int(input())
lis = deque()

ans = 0
for i in range(n):
    a = int(input())
    if i == 0:
        lis.append(a)
        continue
    l = bisect.bisect_left(lis,a)
    r = bisect.bisect_right(lis,a)
    if l != r :
        if l > 0:
            lis[l-1]=a
        elif r ==  len(lis):
            lis.append(a)
        else:
            lis.appendleft(a)
    elif l == 0:
        lis.appendleft(a)
    else:
        lis[r-1] = a
print(len(lis))

Solution (Python):
N = int(input())
l = [-1 for i in range(N)]
for i in range(N):
  A = int(input())
  ok = N-1
  ng = -1
  while abs(ok-ng) > 1:
    mid = (ok+ng)//2
    if l[mid] < A:
      ok = mid
    else:
      ng = mid  
  l[ok] = A

for i in range(N):
  if l[i] == -1:
    ans = i
    break
  
  if i == N-1:
    ans = N  
print(ans)

Solution (Python):
N = int(input())
l = [-1 for i in range(N)]
for i in range(N):
  A = int(input())
  ok = N-1
  ng = -1
  while abs(ok-ng) > 1:
    mid = (ok+ng)//2
    if l[mid] < A:
      ok = mid
    else:
      ng = mid  
  l[ok] = A

for i in range(N):
  if l[i] == -1:
    ans = i
    break
  
  if i == N-1:
    ans = N  
print(ans)

Solution (Python):
from bisect import bisect_right

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

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

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

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

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

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

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

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

Solution (Python):

import sys
input = sys.stdin.readline









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

from collections import deque
from bisect import bisect_left

D = deque([])

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

print(len(D))

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

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

Solution (Python):
import bisect
from collections import deque
def LIS(a):
    lis = deque()
    lis.append(-1)
    for i in range(len(a)):
        index = bisect.bisect_left(lis,a[i])
        if index == 0:
            lis.appendleft(a[i])
        else:
            lis[index-1] = a[i]
    return len(lis)

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

if __name__ == "__main__":
    main()

Solution (Python):
import bisect
from collections import deque

N = int(input())

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

Solution (Python):
import bisect
import sys
input = sys.stdin.readline
N = int(input())
A = [int(input()) for _ in range(N)]

dp = [float('inf')]*(N+1)
for a in A[::-1]:
  idx = bisect.bisect_right(dp, a)
  dp[idx] = a

ans = 0
for n in dp:
  if n != float('inf'):
    ans += 1
print(ans)

Solution (Python):
import bisect
n = int(input())
A = list(int(input()) for _ in range(n))
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)]

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

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

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

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

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

Solution (Python):
import bisect
N=int(input())
ls=[int(input()) for _ in range(N)]
color=[ls[-1]]
ans=1
for i in range(N-1):
  a=ls[-2-i]
  k=bisect.bisect_right(color,a)
  if k==ans:
    color.append(a)
    ans+=1
  else:
    color[k]=a
print(ans)

Solution (Python):
import bisect
N = int(input())
A = list()
for i in range(N):
  A.append(int(input()))
L = list()
for j in range(N-1, -1, -1):
  n = A[j]
  if(len(L) == 0):
    L.append(n)
  elif(L[-1] <= n):
    L.append(n)
  else:
    x = bisect.bisect_right(L, n)
    L[x] = n
print(len(L))

Solution (Python):
ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))

n = ii()
alis = []
for _ in range(n):
    ima = ii()
    ima *= -1
    alis.append(ima)

from bisect import bisect_left as bl
'''index  =  bl(list,num)'''

imaa = [1]*n
for i in range(n):
    index = bl(imaa,alis[i]+1)
    imaa[index] = alis[i]
index = bl(imaa,1)
print(index)

Solution (Python):
from collections import deque

def lower_bound(al, key):
    """
    一般に左側が満たしておらず、右側は満たしている判定基準(境目は一つ)ならlower_boundになる
    (条件を満たすもののうち、最小のインデックスを返す)
    単調にさえなっていれば、左右が逆になっていても検索には使える(ng/okも一緒に逆にする必要がある)
    """
    def isOk(a):
        
        
        return a>=key

    ng = -1
    ok = len(al)

    while abs(ok-ng)>1:
        mid = (ok+ng)//2

        if isOk(al[mid]):
            ok = mid
        else:
            ng = mid

    return ok

n = int(input())
l = deque()

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

    if len(l)==0:
        l.append(a)
        continue

    idx = lower_bound(l,a)
    if idx<1:
        l.appendleft(a)
    else:
        l[idx-1] = a

print(len(l))

Solution (Python):
n=int(input())
a=[int(input()) for _ in range(n)]
from bisect import bisect
b=[]
for i in a:
    j=bisect(b,-i)
    if len(b)==j:
        b.append(-i)
    else:
        b[j]=-i

print(len(b))

Solution (Python):
def LIS(l):
    from bisect import bisect_right
    dp = [l[0]+1]
    for i in range(len(l)):
        if l[i] >= dp[-1]:
            dp.append(l[i])
        else:
            dp[bisect_right(dp, l[i])] = l[i]
    return len(dp)
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())
A = [-int(input()) for _ in range(n)]

B = []
for a in A:
  b = bisect_right(B,a)  
  if len(B) == b:    
    B.append(a)    
  else:
    B[b] = a    
    
print(len(B))

Solution (Python):
from bisect import bisect_right
n = int(input())
A = [-int(input()) for _ in range(n)]

B = []
v = 0
for a in A:
  b = bisect_right(B,a)  
  if v == b:    
    B.append(a)
    v+=1    
  else:
    B[b] = a    
    
print(len(B))

Solution (Python):
import sys
input = sys.stdin.buffer.readline
from bisect import bisect_right
N = int(input())
li_a = []
for _ in range(N):
    a = int(input())
    li_a.append(a)
INF = 10**15
dp = [INF]* N
for i in range(N-1, -1, -1):
    a = li_a[i]
    k = bisect_right(dp, a)
    dp[k] = a
check = INF-1
print(bisect_right(dp, check))

Solution (Python):
import sys, bisect
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = 10**20
def I(): return int(input())
def F(): return float(input())
def S(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()

def lis_(a):
    dp = [INF]*len(a)
    for i in a:
        dp[bisect.bisect_left(dp, i+1)] = i
    return bisect.bisect_left(dp, INF)

def resolve():
    N = I()
    A = [I() for _ in range(N)]
    A = A[::-1]

    print(lis_(A))

if __name__ == '__main__':
    resolve()

Solution (Python):
from random import random
from sys import setrecursionlimit

setrecursionlimit(10 ** 5)


class TreapNode:
    _value = None
    _priority = None
    _count = None
    _left = None
    _right = None

    def __init__(self, value):
        self._value = value
        self._priority = random()
        self._count = 1


def treap_rotate_right(n):
    l = n._left
    n._left = l._right
    l._right = n
    return l


def treap_rotate_left(n):
    r = n._right
    n._right = r._left
    r._left = n
    return r


def treap_insert(n, v):
    if n is None:
        return TreapNode(v)
    if n._value == v:
        n._count += 1
        return n
    if n._value > v:
        n._left = treap_insert(n._left, v)
        if n._priority > n._left._priority:
            n = treap_rotate_right(n)
    else:
        n._right = treap_insert(n._right, v)
        if n._priority > n._right._priority:
            n = treap_rotate_left(n)
    return n


def treap_delete(n, v):
    if n is None:
        return None
    if n._value > v:
        n._left = treap_delete(n._left, v)
        return n
    if n._value < v:
        n._right = treap_delete(n._right, v)
        return n

    
    if n._count > 1:
        n._count -= 1
        return n

    if n._left is None and n._right is None:
        return None

    if n._left is None:
        n = treap_rotate_left(n)
    elif n._right is None:
        n = treap_rotate_right(n)
    else:
        
        if n._left._priority < n._right._priority:
            n = treap_rotate_right(n)
        else:
            n = treap_rotate_left(n)
    return treap_delete(n, v)


def treap_size(n):
    if n is None:
        return 0
    return n._count + treap_size(n._left) + treap_size(n._right)


def treap_str(n):
    if n is None:
        return ""
    result = []
    if n._left is not None:
        result.append(treap_str(n._left))
    result.append("%d:%d" % (n._value, n._count))
    if n._right is not None:
        result.append(treap_str(n._right))
    return ' '.join(result)


def treap_search(n, v):
    
    if n is None:
        return None
    if n._value >= v:
        if n._left is None:
            return None
        return treap_search(n._left, v)
    
    if n._right is None:
        return n
    r = treap_search(n._right, v)
    if r is None:
        return n
    return r


class Treap:
    _root = None

    def insert(self, v):
        self._root = treap_insert(self._root, v)

    def delete(self, v):
        self._root = treap_delete(self._root, v)

    def __len__(self):
        return treap_size(self._root)

    def __str__(self):
        return treap_str(self._root)

    def search(self, v):
        return treap_search(self._root, v)


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

t = Treap()
for a in A:
    n = t.search(a)
    if n is not None:
        t.delete(n._value)
    t.insert(a)
print(len(t))

Solution (Python):
from random import random
from sys import setrecursionlimit

setrecursionlimit(10 ** 5)


class TreapNode:
    _value = None
    _priority = None
    _count = None
    _left = None
    _right = None

    def __init__(self, value):
        self._value = value
        self._priority = random()
        self._count = 1


def treap_rotate_right(n):
    l = n._left
    n._left = l._right
    l._right = n
    return l


def treap_rotate_left(n):
    r = n._right
    n._right = r._left
    r._left = n
    return r


def treap_insert(n, v):
    if n is None:
        return TreapNode(v)
    if v == n._value:
        n._count += 1
        return n
    if v < n._value:
        n._left = treap_insert(n._left, v)
        if n._priority > n._left._priority:
            n = treap_rotate_right(n)
    else:
        n._right = treap_insert(n._right, v)
        if n._priority > n._right._priority:
            n = treap_rotate_left(n)
    return n


def treap_delete(n, v):
    if n is None:
        return None
    if n._value > v:
        n._left = treap_delete(n._left, v)
        return n
    if n._value < v:
        n._right = treap_delete(n._right, v)
        return n

    
    if n._count > 1:
        n._count -= 1
        return n

    if n._left is None and n._right is None:
        return None

    if n._left is None:
        n = treap_rotate_left(n)
    elif n._right is None:
        n = treap_rotate_right(n)
    else:
        
        if n._left._priority < n._right._priority:
            n = treap_rotate_right(n)
        else:
            n = treap_rotate_left(n)
    return treap_delete(n, v)


def treap_size(n):
    if n is None:
        return 0
    return n._count + treap_size(n._left) + treap_size(n._right)


def treap_str(n):
    if n is None:
        return ""
    result = []
    if n._left is not None:
        result.append(treap_str(n._left))
    result.append("%d:%d" % (n._value, n._count))
    if n._right is not None:
        result.append(treap_str(n._right))
    return ' '.join(result)


def treap_search(n, v):
    
    if n is None:
        return None
    if n._value >= v:
        if n._left is None:
            return None
        return treap_search(n._left, v)
    
    if n._right is None:
        return n
    r = treap_search(n._right, v)
    if r is None:
        return n
    return r


class Treap:
    _root = None

    def insert(self, v):
        self._root = treap_insert(self._root, v)

    def delete(self, v):
        self._root = treap_delete(self._root, v)

    def __len__(self):
        return treap_size(self._root)

    def __str__(self):
        return treap_str(self._root)

    def search(self, v):
        return treap_search(self._root, v)


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

t = Treap()
for a in A:
    n = t.search(a)
    if n is not None:
        t.delete(n._value)
    t.insert(a)
print(len(t))

Solution (Python):
from random import random
from sys import setrecursionlimit

setrecursionlimit(3 * 10 ** 5)


class TreapNode:
    _value = None
    _priority = None
    _count = None
    _left = None
    _right = None

    def __init__(self, value):
        self._value = value
        self._priority = random()
        self._count = 1


def treap_rotate_right(n):
    l = n._left
    n._left = l._right
    l._right = n
    return l


def treap_rotate_left(n):
    r = n._right
    n._right = r._left
    r._left = n
    return r


def treap_insert(n, v):
    if n is None:
        return TreapNode(v)
    if v == n._value:
        n._count += 1
        return n
    if v < n._value:
        n._left = treap_insert(n._left, v)
        if n._priority > n._left._priority:
            n = treap_rotate_right(n)
    else:
        n._right = treap_insert(n._right, v)
        if n._priority > n._right._priority:
            n = treap_rotate_left(n)
    return n


def treap_delete(n, v):
    if n is None:
        return None
    if n._value > v:
        n._left = treap_delete(n._left, v)
        return n
    if n._value < v:
        n._right = treap_delete(n._right, v)
        return n

    
    if n._count > 1:
        n._count -= 1
        return n

    if n._left is None and n._right is None:
        return None

    if n._left is None:
        n = treap_rotate_left(n)
    elif n._right is None:
        n = treap_rotate_right(n)
    else:
        
        if n._left._priority < n._right._priority:
            n = treap_rotate_right(n)
        else:
            n = treap_rotate_left(n)
    return treap_delete(n, v)


def treap_size(n):
    if n is None:
        return 0
    return n._count + treap_size(n._left) + treap_size(n._right)


def treap_str(n):
    if n is None:
        return ""
    result = []
    if n._left is not None:
        result.append(treap_str(n._left))
    result.append("%d:%d" % (n._value, n._count))
    if n._right is not None:
        result.append(treap_str(n._right))
    return ' '.join(result)


def treap_search(n, v):
    
    if n is None:
        return None
    if n._value >= v:
        if n._left is None:
            return None
        return treap_search(n._left, v)
    
    if n._right is None:
        return n
    r = treap_search(n._right, v)
    if r is None:
        return n
    return r


class Treap:
    _root = None

    def insert(self, v):
        self._root = treap_insert(self._root, v)

    def delete(self, v):
        self._root = treap_delete(self._root, v)

    def __len__(self):
        return treap_size(self._root)

    def __str__(self):
        return treap_str(self._root)

    def search(self, v):
        return treap_search(self._root, v)


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

t = Treap()
for a in A:
    n = t.search(a)
    if n is not None:
        t.delete(n._value)
    t.insert(a)
print(len(t))

Solution (Python):
from sys import stdin, setrecursionlimit
from bisect import bisect_right

setrecursionlimit(10 ** 9)
INF = 1 << 60


def input():
    return stdin.readline().strip()


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

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

    print(len(B))


if __name__ == '__main__':
    main()