#include <bits/stdc++.h>
using namespace std;
int main() {
  ios_base::sync_with_stdio(0);
  long n, i, k, s, x, p;
  while (cin >> n) {
    long r1 = 0, r2 = 0, r = 1, mx = 0, c = 0, pos;
    pair<long, long> p[100002];
    for (i = 0; i < n; i++) {
      cin >> x;
      p[i] = make_pair(x, i + 1);
    }
    sort(p, p + n);
    pos = p[0].second;
    c = 1;
    for (i = 1; i < n; i++) {
      if (pos < p[i].second)
        c++;
      else {
        mx = max(mx, c);
        c = 1;
      }
      pos = p[i].second;
    }
    mx = max(mx, c);
    cout << n - mx << endl;
  }
  return 0;
}
