#include <cstdio>
#define N 5050
#define inf 1000000100
int n;
int v[N], l[N];
bool pupu[N];

void din()
{
	l[1]=1;
	int max;
	for (int i=2;i<=n;++i)
	{
		l[i]=inf;
		max=0-inf;
		for (int j=i-1;j;--j)
			if (v[j]<=v[i]&&v[j]>max&&l[j]+1<l[i])
			{
				max=v[j];
				l[i]=l[j]+1;
				pupu[j]=1;
			}
		if (l[i]==inf)
			l[i]=1;
	}
}

int main()
{
	freopen ("subsir2.in","r",stdin);
	freopen ("subsir2.out","w",stdout);
	scanf("%d",&n);
	for (int i=1;i<=n;++i)
		scanf("%d",&v[i]);
	din();
	int min=inf;
	for (int i=1;i<=n;++i)
		if (!pupu[i]&&l[i]<min)
			min=l[i];
	printf("%d\n",min);
	return 0;
}