#include <bits/stdc++.h>
using namespace std;
const int maxN = 100002;
int pos[maxN];
int dpf[maxN];
int dpb[maxN];
int DP(int n) {
  int ret = n - 1;
  dpf[0] = dpb[0] = dpf[n + 1] = dpb[n + 1] = 0;
  for (int i = 1; i <= n; i++) {
    dpf[i] = pos[i - 1] < pos[i] ? dpf[i - 1] + 1 : 1;
  }
  for (int i = n; i >= 1; i--) {
    dpb[i] = pos[i + 1] > pos[i] ? dpb[i + 1] + 1 : 1;
  }
  for (int i = 1; i <= n; i++) {
    int sum = (i - dpf[i]) + (n - i + 1 - dpb[i]);
    ret = min(ret, sum);
  }
  return ret;
}
int main() {
  int n;
  while (scanf("%d", &n) != EOF) {
    for (int i = 1; i <= n; i++) {
      int tmp;
      scanf("%d", &tmp);
      pos[tmp] = i;
    }
    pos[0] = 0;
    pos[n + 1] = n + 1;
    printf("%d\n", DP(n));
  }
  return 0;
}
