import std.algorithm;
import std.array;
import std.container;
import std.conv;
import std.math;
import std.numeric;
import std.range;
import std.stdio;
import std.string;
import std.typecons;

void scan(T...)(ref T a) {
    string[] ss = readln.split;
    foreach (i, t; T) a[i] = ss[i].to!t;
}
T read(T)() { return readln.chomp.to!T; }
T[] reads(T)() { return readln.split.to!(T[]); }
alias readint = read!int;
alias readints = reads!int;

int calc(int[] a) {
    int n = cast(int)a.length;
    auto indices = new int[n];
    for (int i = 0; i < n; i++) {
        indices[a[i]-1] = i;
    }

    int maxlen = 1;
    int len = 1;
    for (int i = 1; i < n; i++) {
        if (indices[i-1] < indices[i]) {
            len++;
            maxlen = max(maxlen, len);
        }
        else len = 1;
    }
    return n - maxlen;
}

void main() {
    int n = readint;
    int[] a;
    foreach (_; 0..n) a ~= readint;

    writeln(calc(a));
}
