#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
const int maxn = 100000 + 5;
const long double eps = 1e-6;
long double PI = acos((long double)(-1));
int n;
int a[maxn], trank[maxn];
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
  for (int i = 1; i <= n; i++) trank[a[i]] = i;
  int t = 1, maxi = -0x7FFFFFFF;
  for (int i = 2; i <= n; i++)
    if (trank[i] > trank[i - 1])
      t++;
    else {
      maxi = max(maxi, t);
      t = 1;
    }
  maxi = max(maxi, t);
  printf("%d\n", n - maxi);
  return 0;
}
