#include <bits/stdc++.h>
using namespace std;
const int N = 100500;
int t[N * 3], a[N], d[N], pos[N];
int get_max(int l, int r) {
  int res = 0;
  while (l <= r) {
    if (l % 2 == 1) {
      res = max(t[l], res);
    }
    if (r % 2 == 0) {
      res = max(t[r], res);
    }
    l = (l + 1) / 2;
    r = (r - 1) / 2;
  }
  return res;
}
void upd(int p) {
  while (p) {
    p /= 2;
    t[p] = max(t[p * 2], t[p * 2 + 1]);
  }
}
int main() {
  srand(time(NULL));
  int n;
  cin >> n;
  int sz = 1;
  while (sz <= n) {
    sz *= 2;
  }
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    pos[a[i]] = i;
  }
  int mx = 0;
  for (int i = 1; i <= n; i++) {
    d[i] = d[pos[a[i] - 1]] + 1;
    mx = max(mx, d[i]);
  }
  cout << n - mx;
  return 0;
}
