#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 10e6 + 6;
int p[N];
int nx[N];
int n;
priority_queue<int> r;
bool vis[N];
int main(void) {
  ios::sync_with_stdio(false);
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> p[i];
    nx[p[i] - 1] = i;
  }
  r.push(1);
  for (int i = 1; i <= n; i++) {
    if (!vis[i]) {
      vis[i] = true;
      if (nx[p[i]] > i and nx[p[i]] > 0 and nx[p[i]] <= n) {
        int j = nx[p[i]];
        int ct = 2;
        while (nx[p[j]] > j and nx[p[j]] > 0 and nx[p[j]] <= n) {
          vis[j] = true;
          j = nx[p[j]];
          ct++;
        }
        r.push(ct);
      }
    }
  }
  memset(vis, false, sizeof(vis));
  cout << n - r.top() << endl;
  return 0;
}
