#include <bits/stdc++.h>
using namespace std;
struct Input {
  inline Input &operator,(int &a) { scanf("%d", &a); }
  inline Input &operator,(long int &a) { scanf("%ld", &a); }
  inline Input &operator,(long long &a) { scanf("%lld", &a); }
  inline Input &operator,(float &a) { scanf("%f", &a); }
  inline Input &operator,(char ch) { scanf("%s", &ch); }
  inline Input &operator,(double &d) { scanf("%lf", &d); }
  template <typename T>
  inline Input &operator,(T &a) {
    cin >> a;
  }
} input;
void write(int *p0, int *p1) {
  while (p0 != p1) {
    printf("%d%c", *p0, " \n"[p0 + 1 == p1]);
    p0++;
  }
}
template <class T>
inline T bigMod(T p, T e, T M) {
  long long ret = 1;
  while (e > 0) {
    if (e & 1) ret = (ret * p) % M;
    p = (p * p) % M;
    e >>= 1;
  }
  return (T)ret;
}
template <class T>
inline T power(T p, T e) {
  long long ret = 1;
  while (e > 0) {
    if (e & 1) ret = (ret * p);
    p = (p * p);
    e >>= 1;
  }
  return (T)ret;
}
int dist[1000000 + 10];
int main() {
  int n, ans = INT_MAX;
  cin >> n;
  vector<int> vc(n + 1);
  for (int i = (1); i < (n + 1); i++) cin >> vc[i];
  for (int i = (1); i < (n + 1); i++) {
    if (!dist[vc[i] - 1]) {
      dist[vc[i]] = 1;
    } else {
      dist[vc[i]] = dist[vc[i] - 1] + 1;
    }
    ans = min(ans, n - dist[vc[i]]);
  }
  cout << ans << endl;
  return 0;
}
