#include <bits/stdc++.h>
using namespace std;
int n, a[100005], pos[100005], f[100005], ans = 0;
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
  for (int i = 1; i <= n; ++i) pos[a[i]] = i;
  for (int i = 1; i <= n; ++i)
    ans = max(ans, f[i] = pos[a[i] - 1] < i ? f[pos[a[i] - 1]] + 1 : 1);
  printf("%d", n - ans);
  return 0;
}
