#include <fstream>
#include <algorithm>

using namespace std;

ifstream inf("scmax.in");
ofstream outf("scmax.out");

const int NMAX = 100000;

int v[NMAX];
int sir[NMAX];
int sirpoz[NMAX];
int ant[NMAX];
int sirlen[NMAX];

int main() {
    int n;
    inf >> n;
    for(int i = 0; i < n; i++) {
        inf >> v[i];
    }
    sir[0] = v[0];
    sirpoz[0] = 0;
    ant[0] = -1;
    int len = 1;
    for(int i = 1; i < n; i++) {
        if(v[i] < sir[0]) {
            sir[0] = v[i];
            ant[i] = ant[sirpoz[0]];
            sirpoz[0] = i;
            sirlen[0] = 1;
        }
        else if(v[i] > sir[len - 1]) {
            sir[len] = v[i];
            ant[i] = sirpoz[len - 1];
            sirpoz[len] = i;
            sirlen[len] = sirlen[len - 1] + 1;
            len++;
        }
        else {
            int poz = lower_bound(sir, sir + len, v[i]) - sir;
            sir[poz] = v[i];
            ant[i] = sirpoz[poz];
            sirpoz[poz] = i;
        }
    }
    int maxim = 0;
    for(int i = 0; i < n; i++) {
        if(sirlen[i] > maxim) {
            maxim = sirlen[i];
        }
    }
    outf << maxim;
    outf << '\n';
    return 0;
}