#include <bits/stdc++.h>
using namespace std;
const int MXN = 1e5 + 1;
int n, dp[MXN], k[MXN], ans = 1, rg[MXN], res, maxi;
int main() {
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> k[i];
    dp[k[i]] += dp[k[i] - 1] + 1;
  }
  for (int i = 1; i <= n; i++) {
    if (dp[k[i]] > maxi) {
      maxi = dp[k[i]];
    }
  }
  cout << n - maxi;
  return 0;
}
