#include <bits/stdc++.h>
using namespace std;
int arr[100001];
int main() {
  int n, x, y;
  scanf("%d", &n);
  for (int i = 0; i < n; i++) {
    scanf("%d", &x);
    arr[x] = i;
  }
  x = y = 1;
  for (int i = 1; i < n; i++) {
    if (arr[i] < arr[i + 1])
      x++;
    else {
      y = max(x, y);
      x = 1;
    }
  }
  printf("%d", n - max(x, y));
}
