#include <bits/stdc++.h>
using namespace std;
int f[100000 + 5], id[100000 + 5], p[100000 + 5], n, ans;
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &p[i]);
    id[p[i]] = i;
  }
  for (int i = n; i >= 1; i--) {
    f[i] = (id[p[i] + 1] > i ? f[id[p[i] + 1]] + 1 : 1);
    ans = max(ans, f[i]);
  }
  printf("%d", n - ans);
}
