#include <bits/stdc++.h>
using namespace std;
template <typename T>
inline T abs(T t) {
  return t < 0 ? -t : t;
}
const long long modn = 1000000007;
inline long long mod(long long x) { return x % modn; }
const int MAXN = 100010, INF = 0x3f3f3f3f;
int n, m, deg, s[MAXN], p[MAXN];
int main() {
  scanf("%d", &n);
  for (int a = 0; a < n; a++) {
    scanf("%d", &s[a]);
    p[s[a]] = a;
  }
  int ult = -1, cnt = 0, res = 0;
  for (int a = 1; a <= n; a++) {
    if (p[a] > ult) {
      cnt++;
      ult = p[a];
      res = max(cnt, res);
    } else {
      cnt = 1;
      ult = p[a];
    }
  }
  printf("%d\n", n - res);
  return 0;
}
