#include <bits/stdc++.h>
using namespace std;
int main() {
  int a[100005] = {0}, d[100005], n, i, count = 1, mc = 0;
  cin >> n;
  for (i = 1; i <= n; i++) {
    cin >> a[i];
    d[a[i]] = i;
  }
  for (i = 1; i < n; i++) {
    if (d[i] < d[i + 1]) {
      count++;
    } else {
      mc = max(count, mc);
      count = 1;
    }
  }
  mc = max(count, mc);
  cout << n - mc << endl;
  return 0;
}
