#include <bits/stdc++.h>
using namespace std;
void in() {}
int main() {
  in();
  int n;
  cin >> n;
  int arr[n + 10], ps[n + 10];
  for (int i = 0; i < n; ++i) {
    scanf("%d", arr + i);
    ps[arr[i]] = i + 1;
  }
  ps[0] = ps[n + 1] = -1;
  int a = 0, pre = 1;
  for (int i = 1; i <= n + 1; ++i) {
    if (ps[i - 1] < ps[i]) continue;
    a = max(a, i - pre);
    pre = i;
  }
  cout << (n - a) << endl;
  return 0;
}
