#include <bits/stdc++.h>
int mx_len[1000000], n;
int main() {
  while (scanf("%d", &n) != EOF) {
    int i, a, ans = 0;
    for (i = 1; i <= n; i++) {
      mx_len[i] = 0;
    }
    for (i = 0; i < n; i++) {
      scanf("%d", &a);
      mx_len[a] = mx_len[a - 1] + 1;
      if (mx_len[a] > ans) ans = mx_len[a];
    }
    printf("%d\n", n - ans);
  }
  return 0;
}
