#include <fstream>
#include <algorithm>
using namespace std;
#define dim 5001
int v[dim],a[dim],b[dim],best[dim];

int val(int x,int y)
{
	if(x>y)
		return x;
	return y;
};

int main()
{
	ifstream fin("secv.in");
	ofstream fout("secv.out");
	int i, n,m=1,j,maxim=1;
	fin>>n;
	
	for(i=1;i<=n;++i)
	{
		fin>>v[i];
		a[i]=v[i];
	}
	sort(a+1,a+n+1);
	
	for(i=1;i<=n;++i)
	{
		while(a[i]==a[i+1])
			++i;
		b[m]=a[i];
		++m;
	}
	--m;
	best[1]=1;
	for(i=1;i<=n;++i)
	{
		for(j=i-1;j>=0;--j)
			if(v[i]>v[j])
				best[i]=val(best[j]+1,best[i]);
		maxim=val(maxim,best[i]);
	}
	if(maxim!=m)
		fout<<"1";
	
	return 0;
}