#include <bits/stdc++.h>
using namespace std;
int main() {
  long long n;
  cin >> n;
  vector<long long> p(n);
  for (auto& i : p) cin >> i;
  vector<long long> dp(n, 1);
  vector<int> exist(n, false);
  for (long long i = 0; i < (n); ++i) {
    exist[p[i] - 1] = true;
    if (p[i] != 1)
      if (exist[p[i] - 2]) {
        dp[p[i] - 1] = 1 + dp[p[i] - 2];
      }
  }
  long long max_c = 0;
  for (long long i = 0; i < (n); ++i) max_c = max(max_c, dp[i]);
  cout << n - max_c << endl;
  return 0;
}
