#include <bits/stdc++.h>
using namespace std;
int rint() {
  int t;
  scanf("%d", &t);
  return t;
}
void rint(int& x1) { scanf("%d", &x1); }
void rint(int& x1, int& x2) { scanf("%d%d", &x1, &x2); }
void rint(int& x1, int& x2, int& x3) { scanf("%d%d%d", &x1, &x2, &x3); }
void rint(int& x1, int& x2, int& x3, int& x4) {
  scanf("%d%d%d%d", &x1, &x2, &x3, &x4);
}
long long rll() {
  long long t;
  scanf("%I64d", &t);
  return t;
}
void rll(long long& x1) { scanf("%I64d", &x1); }
void rll(long long& x1, long long& x2) { scanf("%I64d%I64d", &x1, &x2); }
void rll(long long& x1, long long& x2, long long& x3) {
  scanf("%I64d%I64d%I64d", &x1, &x2, &x3);
}
void rll(long long& x1, long long& x2, long long& x3, long long& x4) {
  scanf("%I64d%I64d%I64d%I64d", &x1, &x2, &x3, &x4);
}
double rd() {
  double t;
  scanf("%lf", &t);
  return t;
}
void rd(double& x1) { scanf("%lf", &x1); }
void rd(double& x1, double& x2) { scanf("%lf%lf", &x1, &x2); }
void rd(double& x1, double& x2, double& x3) {
  scanf("%lf%lf%lf", &x1, &x2, &x3);
}
void rd(double& x1, double& x2, double& x3, double& x4) {
  scanf("%lf%lf%lf%lf", &x1, &x2, &x3, &x4);
}
int main() {
  int n = rint();
  int p[n];
  for (int i = 0; i < n; ++i) p[rint() - 1] = i;
  int cur = 1;
  int res = 1;
  for (int i = 0; i < n - 1; ++i) {
    if (p[i] < p[i + 1])
      ++cur;
    else
      cur = 1;
    res = max(res, cur);
  }
  cout << n - res;
  return 0;
}
