#!/usr/bin/env python3
from math import ceil
 
def max_increasing_subseq_length(X):
    L = 0
    M = [None] * (len(X) + 1)
    for i, x in enumerate(X):
        # binary search for the largest positive j <= L such that X[M[j]] < X[i]
        lo, hi = 1, L
        while lo <= hi:
            mid = ceil((lo + hi) / 2)
            if X[M[mid]] < x:
                lo = mid + 1
            else:
                hi = mid - 1
 
        # After searching, lo is 1 greater than the length of the longest
        # prefix of X[i]
        M[lo] = i
        if lo > L:
            L = lo
    return L
 
N, numbers = int(input()), list(map(int, input().split()))
assert len(numbers) == N
print(max_increasing_subseq_length(numbers))

IyEvdXNyL2Jpbi9lbnYgcHl0aG9uMwpmcm9tIG1hdGggaW1wb3J0IGNlaWwKCmRlZiBtYXhfaW5jcmVhc2luZ19zdWJzZXFfbGVuZ3RoKFgpOgogICAgTCA9IDAKICAgIE0gPSBbTm9uZV0gKiAobGVuKFgpICsgMSkKICAgIGZvciBpLCB4IGluIGVudW1lcmF0ZShYKToKICAgICAgICAjIGJpbmFyeSBzZWFyY2ggZm9yIHRoZSBsYXJnZXN0IHBvc2l0aXZlIGogPD0gTCBzdWNoIHRoYXQgWFtNW2pdXSA8IFhbaV0KICAgICAgICBsbywgaGkgPSAxLCBMCiAgICAgICAgd2hpbGUgbG8gPD0gaGk6CiAgICAgICAgICAgIG1pZCA9IGNlaWwoKGxvICsgaGkpIC8gMikKICAgICAgICAgICAgaWYgWFtNW21pZF1dIDwgeDoKICAgICAgICAgICAgICAgIGxvID0gbWlkICsgMQogICAgICAgICAgICBlbHNlOgogICAgICAgICAgICAgICAgaGkgPSBtaWQgLSAxCgogICAgICAgICMgQWZ0ZXIgc2VhcmNoaW5nLCBsbyBpcyAxIGdyZWF0ZXIgdGhhbiB0aGUgbGVuZ3RoIG9mIHRoZSBsb25nZXN0CiAgICAgICAgIyBwcmVmaXggb2YgWFtpXQogICAgICAgIE1bbG9dID0gaQogICAgICAgIGlmIGxvID4gTDoKICAgICAgICAgICAgTCA9IGxvCiAgICByZXR1cm4gTAoKTiwgbnVtYmVycyA9IGludChpbnB1dCgpKSwgbGlzdChtYXAoaW50LCBpbnB1dCgpLnNwbGl0KCkpKQphc3NlcnQgbGVuKG51bWJlcnMpID09IE4KcHJpbnQobWF4X2luY3JlYXNpbmdfc3Vic2VxX2xlbmd0aChudW1iZXJzKSk=

MTAKNCAzIDYgNyA5IDUgMiA4IDcgMw==

10
4 3 6 7 9 5 2 8 7 3