#include <bits/stdc++.h>
using namespace std;
int f[100005], a[100005], i, ans, n, F;
void add(int x, int s) {
  for (; x <= n; x += x & -x) f[x] = max(f[x], s);
}
int ask(int x) {
  int s = 0;
  for (; x; x -= x & -x) s = max(s, f[x]);
  return s;
}
int main() {
  scanf("%d", &n);
  ans = 0;
  for (i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
    if (!f[a[i] - 1])
      f[a[i]] = 1;
    else
      f[a[i]] = f[a[i] - 1] + 1;
    ans = max(ans, f[a[i]]);
  }
  printf("%d\n", n - ans);
}
