#include <bits/stdc++.h>
using namespace std;
const int INF = 1000000000;
const int MAX = 1000000;
const int CNT = 8000;
const int MAXD = 20;
const int BASE = 1000003;
const double eps = 1e-8;
int n;
int A[MAX];
int P[MAX];
int R[MAX];
int main() {
  scanf("%d", &n);
  for (int i = (0); i < (n); i++) {
    scanf("%d", &A[i]);
    --A[i];
  }
  memset(P, -1, sizeof(P));
  int res = 0;
  for (int i = (0); i < (n); i++) {
    R[i] = 1;
    if (A[i] > 0 && P[A[i] - 1] != -1) R[i] = max(R[i], 1 + R[P[A[i] - 1]]);
    P[A[i]] = i;
    res = max(res, R[i]);
  }
  res = n - res;
  printf("%d\n", res);
  return 0;
}
