CodeEff/ECCO huggingface dataset:
# Original solution
import sys
from bisect import bisect_right, insort_left

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

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

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

if __name__ == '__main__':
  main()

# Optimized solution
import sys
from bisect import bisect_right, insort

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

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

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

if __name__ == '__main__':
  main()
# Original solution
import bisect
n = int(eval(input()))
c = [int(eval(input()))]
for i in range(n-1):
  a = int(eval(input()))
  if c[-1] >= a:
    c.append(a)
  else:
    ind = bisect.bisect_left(c[::-1],a)
    c[len(c)-ind] = a
print((len(c)))

# Optimized solution
import bisect
n = int(eval(input()))
a = [int(eval(input())) for i in range(n)]
c = [a[-1]]
for i in a[n-2::-1]:
  if c[-1] <= i:
    c.append(i)
  else:
    c[bisect.bisect_left(c,i+1)] = i
  #print(c)
print((len(c)))
# Original solution
n = int(eval(input()))
a = [int(eval(input())) for i in range(n)]
# n = 6
# a = [5,6,7,2,6,4]

b = [a[0]]
minb = a[0]
count = 1
for i in range(1,n):
    if minb < a[i]:
        for j in range(len(b)):
            if b[j] < a[i]:
                b[j] = a[i]
                minb = min(b)
                break
    else:
        b += [a[i]]
        count += 1
        minb = a[i]

print(count)


# Optimized solution
import bisect

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

b = []
for i in range(n):
    k = bisect.bisect(b,-a[i])
    if k == len(b):
        b.append(-a[i])
    else:
        b[k] = -a[i]

print((len(b)))
# Original solution
# 狭義単調増加部分列
import bisect
from collections import deque

n = int(eval(input()))
A = [int(eval(input())) for _ in range(n)]
que = deque()

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

ans = len(que)
print(ans)


# Optimized solution
import sys
from collections import deque
from bisect import bisect_left

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n = int(eval(input()))
    A = list(int(eval(input())) for _ in range(n))

    LIS = deque()
    for i in range(n):
        if len(LIS) == 0:
            LIS.appendleft(A[i])
        else:
            idx = bisect_left(LIS, A[i])
            if idx == 0:
                LIS.appendleft(A[i])
            else:
                LIS[idx - 1] = A[i]
    print((len(LIS)))


if __name__ == '__main__':
    resolve()
# Original solution
from bisect import bisect_right, insort_right

N = int(eval(input()))
A = [int(eval(input())) for _ in range(N)]
B = [A[-1]]
for a in reversed(A[:-1]):
    idx = bisect_right(B, a)
    if idx == len(B):
        insort_right(B, a)
    else:
        B[idx] = a
        B.sort()
print((len(B)))

# Optimized solution
from bisect import bisect_right

N = int(eval(input()))
A = [int(eval(input())) for _ in range(N)]
B = [A[-1]]
ans = 1
for a in reversed(A[:-1]):
    idx = bisect_right(B, a)
    if idx == ans:
        B.append(a)
        ans += 1
    else:
        B[idx] = a
print(ans)
# Original solution
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 = 10 ** 13
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
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()
A = IR(n)
LIS = [A[0]]
for i in range(1, n):
    if A[i] <= LIS[0]:
        LIS = [A[i]] + LIS
    else:
        LIS[bisect_left(LIS, A[i]) - 1] = A[i]


print((len(LIS)))





# Optimized solution
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 = 10 ** 13
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
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()
A = IR(n)
LIS = deque([A[0]])
for i in range(1, n):
    if A[i] <= LIS[0]:
        LIS.appendleft(A[i])
    else:
        LIS[bisect_left(LIS, A[i]) - 1] = A[i]


print((len(LIS)))
# Original solution
N = int(eval(input()))
A = [int(eval(input())) for _ in range(N)]

from bisect import bisect_left
	
def LIS(L) :
    step = 0
    x = 0
    while True :
        for i in range(x, N) :
            if L[i] >= 0 :
                break
        else :
            break
            
        lis = [L[i]]
        pos = [i]
        x = i
        for p in range(i+1, N) :
            a = L[p]
            if a > lis[-1] :
                lis.append(a)
                pos.append(p)
            elif a >= 0 :
                s = bisect_left(lis, a)
                if lis[s] != a :
                    lis[s] = a
                    pos[s] = p
        # print(pos)
        for p in pos :
            L[p] = -1
        # print(L)
        step += 1
    return step

print((LIS(A)))

# Optimized solution
N = int(eval(input()))
A = [int(eval(input())) for _ in range(N)]

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

print((LIS(A[::-1])))
# Original solution
def bi(l,x,m):
    ok = m
    ng = -1
    while ok - ng > 1:
        mid = (ng+ok)//2
        if l[mid] < x:
            ok = mid
        else:
            ng = mid
    return ok

def bi2(l,x,c,m):
    ok = c
    ng = -1
    while ok - ng > 1:
        mid = (ng+ok)//2
        if l[mid] < x:
            ok = mid
        else:
            ng = mid
    return l[:ok] + [x] + l[ok:c] + l[c+1:]

n = int(eval(input()))
a = [int(eval(input())) for _ in range(n)]
t = [a[0]]
m = 1
for x in a[1:]:
    c = bi(t,x,m)
    if c == m:
        t.append(x)
        m += 1
    else:
        t = bi2(t,x,c,m)
print(m)

# Optimized solution
def bi(l,x):
    ok = len(l)
    ng = -1
    while ok-ng > 1:
        mid = (ng+ok)//2
        if l[mid] < x:
            ok = mid
        else:
            ng = mid
    return ok

n = int(eval(input()))
a = [int(eval(input())) for _ in range(n)]
t = [-1]
m = 1
for x in a:
    c = bi(t,x) 
    if c == m:
        t.append(x)
        m += 1
    else:
        t[c] = x
print(m)
# Original solution
def li():
    return list(map(int, input().split()))


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

    color_list = [-1] * n
    color_num = 0

    for a in a_list:
        # 増分が一番小さいものを選ぶ
        for index, color in enumerate(color_list[:color_num + 1]):
            if color < a:
                color_list[index] = a
                if index == color_num:
                    color_num = color_num + 1
                break
        # color_list[:color_num + 1] = sorted(color_list[:color_num + 1], reverse=True)
        # print(color_list)
    # print()
    # print(color_list)
    print(color_num)

# a1から順番に塗っていく
# 色ごとに、今まで塗った最大値を記録する
# 既存の色でぬれる場合は、なるべく最大値の増分が少なくなるように色を選ぶ
# 既存の色でぬれない場合は新しい色を作って最大値を記録する


# Optimized solution
from bisect import bisect_left


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


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

    color_list = [-1] * n
    color_num = 0

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

# a1から順番に塗っていく
# 色ごとに、今まで塗った最大値を記録する
# 既存の色でぬれる場合は、なるべく最大値の増分が少なくなるように色を選ぶ
# 既存の色でぬれない場合は新しい色を作って最大値を記録する
# Original solution
n=int(eval(input()))
a=[int(eval(input())) for i in range(n)]
ans=0
INF=-10**9
k=0
while max(a)>=0:
  de=[]
  f=a[k]
  de.append(k)
  if f<0:
    k+=1
    continue
  for i in range(k+1,n):
    if f<a[i]:
      de.append(i)
      f=a[i]
  for i in de:
    a[i]=INF
  ans+=1
  k+=1
print(ans)

# Optimized solution
import bisect
n=int(eval(input()))
a=[int(eval(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)))
# Original solution
from bisect import bisect_left
from collections import deque

n = int(eval(input()))
a = tuple(int(eval(input())) for _ in range(n))

d = deque()

for ai in a:
    p = bisect_left(d, ai)  # aa以上の最小値のindex
    if p == 0:
        d.appendleft(ai)
    else:
        d[p - 1] = ai
ans = len(d)
print(ans)

# Optimized solution
from bisect import bisect_left
from collections import deque

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

q = deque([-1])
for x in a:
    insert_pos = bisect_left(q, x) - 1
    # bisect_left[0,len(lis)] == 以上の最小
    # 手前は未満の最大[-1,len(lis))
    if insert_pos == -1:
        q.appendleft(x)
    else:
        q[insert_pos] = x

ret = len(q)

print(ret)

# 最小パス被覆
# Original solution
n = int(eval(input()))
a = [int(eval(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+1
        if a[k] < x:
            i = k
        else:
            j = k - 1
    if a[0] >= x:
        i -= 1
    return i


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


# Optimized solution
n = int(eval(input()))
a = [int(eval(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)
# Original solution
n=int(eval(input()))
a=[int(eval(input())) for _ in range(n)]

import bisect
#a=[0,2,3,4,67,8]
#a.sort()
#bisect.bisect_left(a, 4) #被ったら左側のindexを返す
#bisect.bisect_right(a, 4)#被ったら右側のindexを返す

color=[-1]

for aa in a:
    i=bisect.bisect_left(color, aa)
    if i==0:
        color.insert(0,aa)
        #print("insert")
    else:
        color[i-1]=aa
        #print("update")
    #print(color,aa) 
print((len(color)))


# Optimized solution
n=int(eval(input()))
a=[int(eval(input())) for _ in range(n)]

import bisect
#a=[0,2,3,4,67,8]
#a.sort()
#bisect.bisect_left(a, 4) #被ったら左側のindexを返す
#bisect.bisect_right(a, 4)#被ったら右側のindexを返す

color=[1]
lencolor=1
for aa in a:
    aa=-1*aa
    i=bisect.bisect_right(color, aa)
    if i==lencolor:
        color.append(aa)
        lencolor+=1
        #print("insert")
    else:
        color[i]=aa
        #print("update")
    #print(color,aa) 
print(lencolor)
# Original solution
import sys
import bisect

stdin = sys.stdin
 
ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split()))
rs = lambda: stdin.readline().rstrip()  # ignore trailing spaces

N = ri()
A = [ri() for _ in range(N)]
l = []
for a in A:
    i = bisect.bisect_left(l, a)
    if i == 0:
        l = [a] + l
    else:
        l[i-1] = a

print((len(l)))
#39


# Optimized solution
import sys
import bisect

stdin = sys.stdin
 
ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split()))
rs = lambda: stdin.readline().rstrip()  # ignore trailing spaces

N = ri()
INF = 10 ** 18
A = [10 ** 10 - ri() for _ in range(N)]
dp = [INF] * (N+1)
for a in A:
    i = bisect.bisect_right(dp, a)
    dp[i] = a

print((bisect.bisect_left(dp, INF)))
#39 答え見る
# Original solution
import sys
import bisect

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

N = ir()
A = []
for _ in range(N):
    a = ir()
    i = bisect.bisect_left(A, a)
    if i == 0:
        A.insert(0, a)
    else:
        A[i-1] = a

print((len(A)))
# 14

# Optimized solution
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
# マイナスの値にしてLongest Increasing Sequence
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)
# 04
# Original solution
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 = list(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)))


# Optimized solution
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 = list(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)))
# Original solution
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 = list(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)))


# Optimized solution
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 = list(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)))
# Original solution
class BIT:
    def __init__(self, N):
        self.size = N
        self.tree = [0] * (N + 1)
        self.bisect_K = [1 << k for k in reversed(list(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():

    # https://atcoder.jp/contests/abc134/tasks/abc134_e

    N, *A = list(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()


# Optimized solution
class Multiset:
    def __init__(self, N):
        self.N = N
        self.tree = [0] * (N + 1)
        self.bisect_K = [1 << k for k in reversed(list(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():

    # https://atcoder.jp/contests/abc134/tasks/abc134_e

    N, *A = list(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()
# Original solution
import sys, math, itertools, bisect, copy, re
from collections import Counter, deque, defaultdict

# from itertools import accumulate, permutations, combinations, takewhile, compress, cycle
# from functools import reduce
# from math import ceil, floor, log10, log2, factorial
# from pprint import pprint

INF = float('inf')
MOD = 10 ** 9 + 7
EPS = 10 ** -7
sys.setrecursionlimit(1000000)

# N = int(input())
# N,M = [int(x) for x in input().split()]
# V = [[0] * 100 for _ in range(100)]
# A = [int(input()) for _ in range(N)]
# DP = [[0] * 100 for _ in range(100)]
# DP = defaultdict(lambda: float('inf'))

import heapq

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

B = []

for a in A:
    i = 0
    while i < len(B) and B[i] >= a:
        i += 1

    if i != len(B):
        B[i] = a
    else:
        B.append(a)

print((len(B)))

pass


# Optimized solution
import sys, math, itertools, bisect, copy, re
from collections import Counter, deque, defaultdict

# from itertools import accumulate, permutations, combinations, takewhile, compress, cycle
# from functools import reduce
# from math import ceil, floor, log10, log2, factorial
# from pprint import pprint

INF = float('inf')
MOD = 10 ** 9 + 7
EPS = 10 ** -7
sys.setrecursionlimit(1000000)

# N = int(input())
# N,M = [int(x) for x in input().split()]
# V = [[0] * 100 for _ in range(100)]
# A = [int(input()) for _ in range(N)]
# DP = [[0] * 100 for _ in range(100)]
# DP = defaultdict(lambda: float('inf'))

import heapq

N = int(eval(input()))
A = []
for _ in range(N):
    A.append(-int(eval(input())))

B = []

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

# print(B)
print((len(B)))

pass
# Original solution
N = int(eval(input()))
X = []
for i in range(N):
    A = int(eval(input()))
    for j in range(len(X)):
        if A > X[j]:
            X[j] = A
            break
    else:
        X.append(A)
print((len(X)))


# Optimized solution
import bisect

N = int(eval(input()))
A = [-int(eval(input())) for i in range(N)]
X = []
for i in range(N):
    a = A[i]
    idx = bisect.bisect_left(X, a+0.1)
    if idx == len(X):
        X.append(a)
    else:
        X[idx] = a
print((len(X)))
# Original solution
import bisect

N = int(eval(input()))
A = [-int(eval(input())) for i in range(N)]
X = []
for i in range(N):
    a = A[i]
    idx = bisect.bisect_left(X, a+0.1)
    if idx == len(X):
        X.append(a)
    else:
        X[idx] = a
print((len(X)))

# Optimized solution
import bisect

N = int(eval(input()))
A = [-int(eval(input())) for i in range(N)]
X = []
for i in range(N):
    a = A[i]
    idx = bisect.bisect(X, a)
    if idx == len(X):
        X.append(a)
    else:
        X[idx] = a
print((len(X)))