#include <bits/stdc++.h>
using namespace std;
int a[100100], inv[100100];
bool sgn[100100] = {0};
int main() {
  int n;
  cin >> n;
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
    inv[a[i]] = i;
  }
  for (int i = 1; i < n; i++)
    if (inv[i] < inv[i + 1]) sgn[i] = 1;
  int cnt, lead = 1;
  for (int i = 1; i < n; i++) {
    cnt = 1;
    while (sgn[i] != 0) {
      cnt++;
      i++;
    }
    if (lead < cnt) lead = cnt;
  }
  cout << n - lead << endl;
  return 0;
}
