#include <stdio.h>
#include <string.h>

#define Dim 5001

int v[Dim],d[Dim],q[Dim];
char use[Dim];

int BS(int x,int L,int R)
{
	if(L<=R)
	{
		int M=L+(R-L)/2;

		if(x<v[q[M]]) return BS(x,L,M-1);
		else return BS(x,M+1,R);
	}
	else return L;
}

int main()
{
	int N,i,size,pos,max;

	freopen("subsir2.in","r",stdin);

	scanf("%d",&N);
	for(i=1;i<=N;i++) scanf("%d",&v[i]);

	memset(d,0,sizeof(d));
	memset(q,0,sizeof(q));
	memset(use,0,sizeof(use));

	d[1]=1;
	q[1]=1;
	size=1;

	for(i=2;i<=N;i++)
		if(v[q[size]]<v[i])
		{
			use[q[size]]=1;
			q[++size]=i;
			d[i]=size;
		}
		else
		{
			pos=BS(v[i],1,size);
			use[q[pos]-1]=1;
			q[pos]=i;
			d[i]=pos;
		}

	pos=0;
	max=N+1;

	for(i=1;i<=N;i++)
		if(!use[i])
			if(d[i]<max)
			{
				max=d[i];
				pos=i;
			}

	freopen("subsir2.out","w",stdout);

	printf("%d\n",max);

	return 0;
}