import std.stdio, std.conv, std.string, std.bigint;
import std.math, std.random, std.datetime;
import std.array, std.range, std.algorithm, std.container;
string read(){ static string[] ss; while(!ss.length) ss = readln.chomp.split; string res = ss[0]; ss.popFront; return res; }

void main(){
	
	int n = read.to!int;
	int[] ps;
	foreach(i; 0 .. n) ps ~= read.to!int - 1;
	
	debug writeln("ps:", ps);
	
	bool[] xs = new bool[](n); // xs[i]: number i has already appeard
	bool[] ys = new bool[](n); // ys[i]: number (i + 1) appears later than number i in ps
	foreach(p; ps){
		xs[p] = 1;
		ys[p] = (p < n - 1 && !xs[p + 1]);
		}
	
	debug writeln("xs:", xs);
	debug writeln("ys:", ys);
	
	int ans = 0;
	int temp = 0;
	foreach(y; ys){
		temp += 1;
		if(y == 0){
			if(temp > ans) ans = temp;
			temp = 0;
			}
		debug writeln("y:", y, " ans:", ans, " temp:", temp);
		}
	if(temp > ans) ans = temp;
	
	(n - ans).writeln;
	}