#include <fstream>
#include <algorithm>
using namespace std;

ifstream F("scmax.in");
ofstream G("scmax.out");

#define Nmax 10000
#define first v
#define second p

int N;
int A[Nmax+11];
int B[Nmax+11];
int P[Nmax+11];
int Arb[Nmax*4+11];

int Pos,Beg,End,Val,Max;

void Update(int,int,int);
void Query(int,int,int);

int Find(int val,int A[])
{
    int i, step;
    for (step = 1; step < N; step <<= 1);
    for (i = 0; step; step >>= 1)
        if (i + step < N && A[i + step] <= val)
           i += step;
    return i;
}

int main()
{
	F>>N;

	for (int i=1;i<=N;++i)
		F>>B[i],A[i]=B[i];
	sort(A,A+N+1);

	for (int i=1;i<=N;++i)
		P[i]=Find(B[i],A);

	for (int i=1;i<=N;++i)
	{
		Beg=1,End=P[i],Max=0;
		Query(1,1,N);

		Val=Max+1;Pos=P[i];
		Update(1,1,N);
	}

	/*for (short i=1;i<=N;++i)
	{
		Beg=P[i],End=P[i],Max=0;
		Query(1,1,N);
		Best[i]=Max;
	}*/ // asa se scot valorile intr-un vecotor daca e nevoie

	Beg=1,End=N;
	Query(1,1,N);
	G<<Max<<'\n';
}

void Update(int Nod,int St,int Dr)
{
	if ( St==Dr )
	{
		Arb[Nod]=Val;
		return;
	}

	int Mid=(St+Dr)/2;
	if ( Pos<=Mid )
		Update(2*Nod,St,Mid);
	else
		Update(2*Nod+1,Mid+1,Dr);

	Arb[Nod]=max(Arb[2*Nod],Arb[2*Nod+1]);
}

void Query(int Nod,int St,int Dr)
{
	if ( Beg<=St && Dr<=End )
	{
		Max=max(Max,Arb[Nod]);
		return;
	}

	int Mid= (St+Dr) /2;
	if ( Beg<=Mid )
		Query(2*Nod,St,Mid);
	if ( Mid<End )
		Query(2*Nod+1,Mid+1,Dr);
}