#include <bits/stdc++.h>
#pragma warning(disable : 4786)
using namespace std;
int main() {
  int i, a[100009], n;
  while (scanf("%d", &n) == 1) {
    int pos[100009] = {0};
    for (i = 1; i <= n; i++) {
      scanf("%d", &a[i]);
      pos[a[i]] = i;
    }
    int cnt = 1, mx = 1;
    for (i = 1; i <= n; i++) {
      if (pos[i + 1] > pos[i])
        cnt++;
      else {
        mx = max(mx, cnt);
        cnt = 1;
      }
    }
    printf("%d\n", n - mx);
  }
  return 0;
}
