#include <bits/stdc++.h>
using namespace std;
const int N = 100009;
int m, n, maxi;
bool mark[N];
int a[N], dp[N];
void update(int x) { mark[x - 1] ? dp[x] = dp[x - 1] + 1 : dp[x] = 1; }
int main() {
  ios_base::sync_with_stdio(false);
  cin >> n;
  for (int i = 0; i < n; ++i) {
    cin >> a[i];
    mark[a[i]] = true;
    update(a[i]);
  }
  for (int i = 0; i < n; ++i) maxi = max(maxi, dp[a[i]]);
  cout << n - maxi << '\n';
  return 0;
}
