# -*- coding: utf-8 -*-

# E - Sequence Decomposing

import sys 

from bisect import bisect_left

from collections import deque



read = sys.stdin.buffer.read

readline = sys.stdin.buffer.readline

readlines = sys.stdin.buffer.readlines

N = int(readline())

A = list(map(int,read().split()))





INF = 10**31

q = deque([])



for a in A:

    idx = bisect_left(q, a)

    if idx == 0:

        q.appendleft(a)

    else:

        q[idx-1] = a

print((len(q)))
# -*- coding: utf-8 -*-

# E - Sequence Decomposing

import sys 

from bisect import bisect_right



read = sys.stdin.buffer.read

readline = sys.stdin.buffer.readline

readlines = sys.stdin.buffer.readlines

N = int(readline())

A = list(map(int,read().split()))

X = [-1]*N

for a in A:

    i = bisect_right(X,a-1)-1

    X[i] = a

print((N - X.count(-1))) 
# -*- coding: utf-8 -*-
# E - Sequence Decomposing
import sys
from bisect import bisect_left
from collections import deque

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N = int(readline())
A = list(map(int, read().split()))
INF = 10**31
q = deque([])
for a in A:
    idx = bisect_left(q, a)
    if idx == 0:
        q.appendleft(a)
    else:
        q[idx - 1] = a
print((len(q)))

# -*- coding: utf-8 -*-
# E - Sequence Decomposing
import sys
from bisect import bisect_right

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N = int(readline())
A = list(map(int, read().split()))
X = [-1] * N
for a in A:
    i = bisect_right(X, a - 1) - 1
    X[i] = a
print((N - X.count(-1)))

-from bisect import bisect_left -from collections import deque +from bisect import bisect_right -INF = 10**31 -q = deque([]) +X = [-1] * N -    idx = bisect_left(q, a) -    if idx == 0: -        q.appendleft(a) -    else: -        q[idx - 1] = a -print((len(q))) +    i = bisect_right(X, a - 1) - 1 +    X[i] = a +print((N - X.count(-1)))