#include <bits/stdc++.h>
#pragma comment(linker, "/STACK:256000000")
using namespace std;
const int maxN = 110000;
const int inf = 1000000000;
int n, a[maxN];
int d[maxN];
int main() {
  scanf("%d", &n);
  for (int i = 0; i < n; ++i) {
    scanf("%d", &a[i]);
  }
  int res = 0;
  for (int i = 0; i < n; ++i) {
    d[a[i]] = d[a[i] - 1] + 1;
    res = max(res, d[a[i]]);
  }
  printf("%d\n", n - res);
  return 0;
}
