import sys, re

from collections import deque, defaultdict, Counter

from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd

from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby

from operator import itemgetter, mul

from copy import deepcopy

from string import ascii_lowercase, ascii_uppercase, digits

from bisect import bisect, bisect_left, insort, insort_left

from heapq import heappush, heappop

from functools import reduce

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

def INT(): return int(eval(input()))

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

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

def TUPLE(): return tuple(map(int, input().split()))

def ZIP(n): return list(zip(*(MAP() for _ in range(n))))

sys.setrecursionlimit(10 ** 9)

INF = float('inf')

mod = 10 ** 9 + 7 

#mod = 998244353

from decimal import *

#import numpy as np

#decimal.getcontext().prec = 10



N = INT()

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



color_max = deque([])

cnt = 0



for a in A:

	idx = bisect_left(color_max, a)

	if idx == 0:

		color_max.appendleft(a) 

		cnt += 1

	else:

		color_max[idx-1] = a



print(cnt)
import sys, re

from collections import deque, defaultdict, Counter

from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd

from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby

from operator import itemgetter, mul

from copy import deepcopy

from string import ascii_lowercase, ascii_uppercase, digits

from bisect import bisect, bisect_left, insort, insort_left

from heapq import heappush, heappop

from functools import reduce

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

def INT(): return int(eval(input()))

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

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

def TUPLE(): return tuple(map(int, input().split()))

def ZIP(n): return list(zip(*(MAP() for _ in range(n))))

sys.setrecursionlimit(10 ** 9)

INF = float('inf')

mod = 10 ** 9 + 7 

#mod = 998244353

from decimal import *

#import numpy as np

#decimal.getcontext().prec = 10



N = INT()

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



seq = A[::-1]

LIS = [seq[0]]

for i in range(1, N):

	if LIS[-1] <= seq[i]:

		LIS.append(seq[i])

	else:

		LIS[bisect(LIS, seq[i])] = seq[i]



print((len(LIS)))
import sys, re
from collections import deque, defaultdict, Counter
from math import (
    ceil,
    sqrt,
    hypot,
    factorial,
    pi,
    sin,
    cos,
    tan,
    asin,
    acos,
    atan,
    radians,
    degrees,
    log2,
    gcd,
)
from itertools import (
    accumulate,
    permutations,
    combinations,
    combinations_with_replacement,
    product,
    groupby,
)
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce


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


def INT():
    return int(eval(input()))


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


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


def TUPLE():
    return tuple(map(int, input().split()))


def ZIP(n):
    return list(zip(*(MAP() for _ in range(n))))


sys.setrecursionlimit(10**9)
INF = float("inf")
mod = 10**9 + 7
# mod = 998244353
from decimal import *

# import numpy as np
# decimal.getcontext().prec = 10
N = INT()
A = [INT() for _ in range(N)]
color_max = deque([])
cnt = 0
for a in A:
    idx = bisect_left(color_max, a)
    if idx == 0:
        color_max.appendleft(a)
        cnt += 1
    else:
        color_max[idx - 1] = a
print(cnt)

import sys, re
from collections import deque, defaultdict, Counter
from math import (
    ceil,
    sqrt,
    hypot,
    factorial,
    pi,
    sin,
    cos,
    tan,
    asin,
    acos,
    atan,
    radians,
    degrees,
    log2,
    gcd,
)
from itertools import (
    accumulate,
    permutations,
    combinations,
    combinations_with_replacement,
    product,
    groupby,
)
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce


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


def INT():
    return int(eval(input()))


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


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


def TUPLE():
    return tuple(map(int, input().split()))


def ZIP(n):
    return list(zip(*(MAP() for _ in range(n))))


sys.setrecursionlimit(10**9)
INF = float("inf")
mod = 10**9 + 7
# mod = 998244353
from decimal import *

# import numpy as np
# decimal.getcontext().prec = 10
N = INT()
A = [INT() for _ in range(N)]
seq = A[::-1]
LIS = [seq[0]]
for i in range(1, N):
    if LIS[-1] <= seq[i]:
        LIS.append(seq[i])
    else:
        LIS[bisect(LIS, seq[i])] = seq[i]
print((len(LIS)))

-color_max = deque([]) -cnt = 0 -for a in A: -    idx = bisect_left(color_max, a) -    if idx == 0: -        color_max.appendleft(a) -        cnt += 1 +seq = A[::-1] +LIS = [seq[0]] +for i in range(1, N): +    if LIS[-1] <= seq[i]: +        LIS.append(seq[i]) -        color_max[idx - 1] = a -print(cnt) +        LIS[bisect(LIS, seq[i])] = seq[i] +print((len(LIS)))