import std.algorithm;
import std.stdio;

int solve (int n)
{
	auto p = new int [n];
	auto q = new int [n];
	foreach (i, ref c; p)
	{
		readf (" %s", &c);
		c -= 1;
		q[c] = i;
	}
	int cur = 1;
	int res = cur;
	foreach (i; 1..n)
	{
		if (q[i] > q[i - 1])
		{
			cur += 1;
			res = max (res, cur);
		}
		else
		{
			cur = 1;
		}
	}
	return n - res;
}

void main ()
{
	int n;
	while (readf (" %s", &n) > 0)
	{
		writeln (solve (n));
	}
}
