#include <bits/stdc++.h>
int main() {
  int n, i, j, k;
  int arr[100005];
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &arr[i]);
  }
  int pos[100005];
  for (int i = 1; i <= n; i++) {
    pos[arr[i]] = i;
  }
  int ans[100005] = {0};
  ans[0] = 1;
  j = 0;
  for (int i = 2; i <= n; i++) {
    if (pos[i - 1] < pos[i])
      ans[j]++;
    else {
      j++;
      ans[j]++;
    }
  }
  j++;
  int maxel = ans[0];
  for (int i = 1; i < j; i++) {
    if (maxel < ans[i]) maxel = ans[i];
  }
  printf("%d\n", n - maxel);
  return 0;
}
