#include <bits/stdc++.h>
using namespace std;
int a[100005], pos[100005];
int visit[100005];
int n;
int solve(int curr, int indx) {
  visit[curr] = 1;
  if (curr == n || indx == n) return 0;
  int p = pos[curr + 1];
  int res = 0;
  if (p > indx) {
    res = 1 + solve(curr + 1, p);
  }
  return res;
}
int main() {
  scanf("%d", &n);
  memset(visit, 0, sizeof visit);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
    pos[a[i]] = i;
  }
  int res = 0;
  for (int i = 1; i <= n; i++) {
    if (visit[a[i]] == 0) {
      res = max(res, 1 + solve(a[i], i));
    }
  }
  cout << n - res << endl;
  return 0;
}
