#include <bits/stdc++.h>
using namespace std;
bool equalTo(double a, double b) {
  if (fabs(a - b) <= 1e-9) return true;
  return false;
}
bool notEqual(double a, double b) {
  if (fabs(a - b) > 1e-9) return true;
  return false;
}
bool lessThan(double a, double b) {
  if (a + 1e-9 < b) return true;
  return false;
}
bool lessThanEqual(double a, double b) {
  if (a < b + 1e-9) return true;
  return false;
}
bool greaterThan(double a, double b) {
  if (a > b + 1e-9) return true;
  return false;
}
bool greaterThanEqual(double a, double b) {
  if (a + 1e-9 > b) return true;
  return false;
}
long long GCD(long long a, long long b) {
  if (b == 0) return a;
  return GCD(b, a % b);
}
long long LCM(long long a, long long b) { return a * b / GCD(a, b); }
int pos[100005];
int A[100005];
int N;
int solve() {
  int cnt = 1, Mx = 1;
  for (int i = 2; i <= N; i++) {
    if (pos[i] > pos[i - 1]) {
      cnt++;
      Mx = max(Mx, cnt);
    } else {
      cnt = 1;
    }
  }
  return Mx;
}
int main() {
  scanf("%d", &N);
  for (int i = 1; i <= N; i++) {
    scanf("%d", &A[i]);
    pos[A[i]] = i;
  }
  int res = solve();
  cout << (N - res) << endl;
}
