#include <bits/stdc++.h>
using namespace std;
int n, a[100005], que[100005], maxn, pos, minn = 1000005;
int main() {
  cin >> n;
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
  for (int i = 1; i <= n; i++) {
    que[a[i]] = que[a[i] - 1] + 1;
    maxn = max(maxn, que[a[i]]);
  }
  cout << n - maxn;
  return 0;
}
