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