#include <bits/stdc++.h>
using namespace std;
int p[100010];
int n, b;
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  ;
  cin >> n;
  for (int i = (0); i < (int)(n); i++) cin >> b, p[b - 1] = i;
  int lmx = 1, mx = 1;
  for (int i = (1); i < (int)(n); i++) {
    if (p[i] > p[i - 1])
      lmx++;
    else
      lmx = 1;
    mx = max(mx, lmx);
  }
  cout << n - mx << endl;
}
