#include <bits/stdc++.h>
using namespace std;
int pos[1000001];
int n, x;
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &x);
    pos[x] = i;
  }
  pos[n + 1] = 0;
  int ans = n, bf = 1;
  for (int i = 2; i <= n + 1; i++) {
    if (pos[i] < pos[i - 1]) {
      ans = min(ans, n - bf);
      bf = 1;
    } else
      bf++;
  }
  printf("%d\n", ans);
}
