#include <bits/stdc++.h>
using namespace std;
const int inf = (int)1e9;
const long long mod = (long long)1e9 + 7;
const double eps = (double)1e-9;
const double pi = acos(-1.0);
const int dx[] = {0, 0, 1, 0, -1};
const int dy[] = {0, 1, 0, -1, 0};
const int N = 100500;
int n, ans, a[N], dp[N];
int main() {
  cin >> n;
  for (int i = 1; i <= n; i++) cin >> a[i];
  ans = inf;
  for (int i = 1; i <= n; i++) {
    dp[a[i]] = dp[a[i] - 1] + 1;
    ans = min(ans, n - dp[a[i]]);
  }
  cout << ans;
  return 0;
}
