#include <bits/stdc++.h>
using namespace std;
const int maxn = 100010;
int pos[maxn], id[maxn];
bool vis[maxn];
int main() {
  int ans = 0, sum = 0, N, x;
  scanf("%d", &N);
  for (int i = 1; i <= N; ++i) {
    scanf("%d", &x);
    pos[x] = id[x] = i;
    vis[i] = false;
  }
  sum = 1;
  int cnt = 0;
  for (int i = 1; i < N; ++i) {
    if (pos[i + 1] > pos[i]) {
      sum++;
    } else {
      if (cnt < sum) cnt = sum;
      sum = 1;
    }
  }
  if (cnt < sum) cnt = sum;
  cout << (N - cnt) << endl;
  return 0;
}
