#include <bits/stdc++.h>
using namespace std;
int N;
int *A;
int *I;
int *F;
void printArray(int *A, int i, int j);
int main() {
  cin >> N;
  A = (int *)(malloc(N * sizeof(int)));
  I = (int *)(malloc(N * sizeof(int)));
  F = (int *)(malloc(N * sizeof(int)));
  memset(F, 0, N * sizeof(int));
  for (int i = 0; i < N; i++) {
    cin >> A[i];
    I[A[i] - 1] = i;
  }
  F[0] = 1;
  int m = 1;
  for (int i = 1; i < N; i++) {
    if (A[i] == 1)
      F[i] = 1;
    else {
      F[i] = F[I[A[i] - 2]] + 1;
    }
    m = (m > F[i] ? m : F[i]);
  }
  cout << N - m << endl;
}
void printArray(int *A, int i, int j) {
  for (int k = i; k <= j - 1; k++) {
    cout << A[k] << " ";
  }
  cout << A[j] << endl;
}
