#include <iostream>
#include <set>
 
using namespace std;
typedef long long int ll;
 
int main() {
    // Optimize standard I/O operations for performance
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
 
    ll n;
    if (!(cin >> n)) return 0;
 
    multiset<ll> k;
    for (ll i = 0; i < n; i++) {
        ll val;
        cin >> val;
 
        // lower_bound returns an iterator to the first element >= val
        auto it = k.lower_bound(val);
 
        // If it's not the beginning, there is at least one element < val
        if (it != k.begin()) {
            --it; // Move back one step to get the largest element strictly < val
            k.erase(it); // Erase the found element
        }
 
        // Insert the current element
        k.insert(val);
    }
 
    cout << k.size() << "\n";
 
    return 0;
}

I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8c2V0PgoKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKdHlwZWRlZiBsb25nIGxvbmcgaW50IGxsOwoKaW50IG1haW4oKSB7CiAgICAvLyBPcHRpbWl6ZSBzdGFuZGFyZCBJL08gb3BlcmF0aW9ucyBmb3IgcGVyZm9ybWFuY2UKICAgIGlvc19iYXNlOjpzeW5jX3dpdGhfc3RkaW8oZmFsc2UpOwogICAgY2luLnRpZShOVUxMKTsKCiAgICBsbCBuOwogICAgaWYgKCEoY2luID4+IG4pKSByZXR1cm4gMDsKCiAgICBtdWx0aXNldDxsbD4gazsKICAgIGZvciAobGwgaSA9IDA7IGkgPCBuOyBpKyspIHsKICAgICAgICBsbCB2YWw7CiAgICAgICAgY2luID4+IHZhbDsKICAgICAgICAKICAgICAgICAvLyBsb3dlcl9ib3VuZCByZXR1cm5zIGFuIGl0ZXJhdG9yIHRvIHRoZSBmaXJzdCBlbGVtZW50ID49IHZhbAogICAgICAgIGF1dG8gaXQgPSBrLmxvd2VyX2JvdW5kKHZhbCk7CiAgICAgICAgCiAgICAgICAgLy8gSWYgaXQncyBub3QgdGhlIGJlZ2lubmluZywgdGhlcmUgaXMgYXQgbGVhc3Qgb25lIGVsZW1lbnQgPCB2YWwKICAgICAgICBpZiAoaXQgIT0gay5iZWdpbigpKSB7CiAgICAgICAgICAgIC0taXQ7IC8vIE1vdmUgYmFjayBvbmUgc3RlcCB0byBnZXQgdGhlIGxhcmdlc3QgZWxlbWVudCBzdHJpY3RseSA8IHZhbAogICAgICAgICAgICBrLmVyYXNlKGl0KTsgLy8gRXJhc2UgdGhlIGZvdW5kIGVsZW1lbnQKICAgICAgICB9CiAgICAgICAgCiAgICAgICAgLy8gSW5zZXJ0IHRoZSBjdXJyZW50IGVsZW1lbnQKICAgICAgICBrLmluc2VydCh2YWwpOwogICAgfQogICAgCiAgICBjb3V0IDw8IGsuc2l6ZSgpIDw8ICJcbiI7CiAgICAKICAgIHJldHVybiAwOwp9

MTAKMSAyIDMgNCA1IDEgMiAxIDEgMQ==

10
1 2 3 4 5 1 2 1 1 1