/*
TASK:psort
LANG:C++
*/

#include <cstdio>
#include <vector>
#include <algorithm>

typedef signed int ind;

void read_ind(ind& n) {std::scanf("%d", &n);}
void write_ind(const ind& n) {std::printf("%d", n);}
void write(char *s) {std::printf("%s", s);}

int main()
{
	ind n;
	read_ind(n);
	std::vector<ind> perm(n);
	for (ind i = 0; i < n; i++) read_ind(perm[i]);

	std::vector<ind> max_inc;
	for (ind i = 0; i < n; i++)
	{
		const ind& c = perm[i];

		std::vector<ind>::iterator it = std::lower_bound(max_inc.begin(), max_inc.end(), c);
		if (it == max_inc.end())
			max_inc.push_back(c);
		else *it = c;
	}

	write_ind(n-(ind)max_inc.size());
	write("\n");

	return 0;
}
