/* O(n * log n) solution to longest strictly increasing subsequence */
#include <iostream>
#include <string.h>
#include <stdio.h>

#define NMAX 100000
#define FILEIN "scmax.in"
#define FILEOUT "scmax.out"

using namespace std;

int A[NMAX];
int tail[NMAX + 1];
int sol[NMAX];


// Binary search to find the ceil of key in array A (note boundaries in the caller)
int CeilIndex(int A[], int l, int r, int key) {
    int m;

	while ( r - l > 1 ) {
		m = l + (r - l) / 2;
		(A[m] >= key ? r : l) = m;
	}

    return r;
}
 
int LongestIncreasingSubsequenceLength(int A[], int size) {
    // Add boundary case, when array size is one
 
    int len; // always points empty slot
 
    tail[0] = A[0];
	sol[0] = A[0];
    len = 1;
    for ( int i = 1; i < size; i++ ) {
        if( A[i] < tail[0] ) {
            // new smallest value
            tail[0] = A[i];
			if (len == 1) {
				sol[0] = A[i];
			}
		}
        else if( A[i] > tail[len-1] ) {
            // A[i] wants to extend largest subsequence
			sol[len] = A[i];
            tail[len++] = A[i];
		}
        else {
            // A[i] wants to be current end candidate of an existing subsequence
            // It will replace ceil value in tail
            int ceil = CeilIndex(tail, -1, len - 1, A[i]);
            tail[ceil] = A[i];
			if ( ceil == len - 1 && A[i] != sol[len - 2] ) {
				sol[len - 1] = A[i];
			}
		}
    }
 
    return len;
}

void read_file(const char *filename, int &n )
{
	FILE *f = fopen(filename, "r");

	fscanf(f, "%d", &n);

	for ( int i = 0; i < n; i++ ) {
		fscanf(f, "%d", &A[i]);
	}

	fclose(f);
}

void print_res(const char *filename, const int &res)
{
	FILE *f = fopen(filename, "w");

 	fprintf(f, "%d\n", res);

//	for (int i = 0; i < res; i++) {
//		fprintf(f, "%d ", sol[i]);
//	}
//	fprintf(f, "\n");
 
	fclose(f);
}
 
int main()
{
	int n;
 
	read_file(FILEIN, n);

	int res = LongestIncreasingSubsequenceLength(A, n);
 	
	print_res(FILEOUT, res);
    
	return 0;
}