#include <bits/stdc++.h>
using namespace std;
int main() {
  int n, *train;
  cin >> n;
  train = new int[n];
  for (int i = 0; i < n; i++) {
    int tmp;
    cin >> tmp;
    train[tmp - 1] = i;
  }
  int current_length = 1, max_length = 1;
  for (int i = 1; i < n; i++) {
    if (train[i] > train[i - 1]) {
      current_length++;
      if (current_length > max_length) max_length = current_length;
    } else
      current_length = 1;
  }
  cout << n - max_length;
  return 0;
}
