#include <fstream>
using namespace std;

ifstream fin("subsir2.in");
ofstream fout("subsir2.out");

int main()
{
	int a[5001], dp[5001], b[5001] = {};
	int n, i, j, rasp, m;
	fin >> n;
	for (i = 1; i<=n; i++)
	{
		fin >> a[i];
		dp[i] = n+1;
	}
	for (i = n; i>=1; i--)
	{
		if (dp[i] > n)
			dp[i] = 1;
		m = 0;
		for (j = i-1; j>=1; j--)
			if (a[j] <= a[i] && a[j] > m)
			{
				dp[j] = min(dp[j], 1 + dp[i]);
				m = max(m, a[j]);
				b[i] = 1;
			}
	}
	
	rasp = n+1;
	for (i = 1; i<=n; i++)
		if (b[i] == 0)
			rasp = min(rasp, dp[i]);
	fout << rasp;
	return 0;
}