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 ans = 0;
    int end = 0;
    int len = 0;
    for (int beg = 0; beg < n; beg++) {
        while (end < n && (beg == end || indices[end-1] < indices[end])) {
            len++;
            end++;
        }

        ans = max(ans, len);

        if (beg == end) end++;
        else len--;
    }
    return n - ans;
}

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

    writeln(calc(a));
}
