import std.stdio;
import std.range;
import std.array;
import std.string;
import std.conv;
import std.typecons;
import std.algorithm;
import std.container;
import std.typecons;
import std.random;
import std.csv;
import std.regex;
import std.math;
import core.time;
import std.ascii;
import std.digest.sha;
import std.outbuffer;
import std.numeric;
import std.bigint;

void main()
{
	int n = readln.chomp.to!int;
	int[] p = new int[](n);
	foreach (ref v; p) {
		v = readln.chomp.to!int;
	}
	bool[] done = new bool[](n + 1);
	int[] memo = new int[](n + 1);
	foreach (v; p) {
		if (done[v - 1]) {
			memo[v] = memo[v - 1];
		} else {
			memo[v] = v;
		}
		done[v] = true;
	}
	int ans = 0;
	foreach (v; p) {
		ans = max(ans, v - memo[v]);
	}
	++ans;
	ans = n - ans;
	ans.writeln;
}

void tie(R, Args...)(R arr, ref Args args)
		if (isRandomAccessRange!R || isArray!R)
in
{
	assert (arr.length == args.length);
}
body
{
	foreach (i, ref v; args) {
		alias T = typeof(v);
		v = arr[i].to!T;
	}
}

void verbose(Args...)(in Args args)
{
	stderr.write("[");
	foreach (i, ref v; args) {
		if (i) stderr.write(", ");
		stderr.write(v);
	}
	stderr.writeln("]");
}
