#include <bits/stdc++.h>
using namespace std;
int cars[100100];
int dp[100100];
int main() {
  int n;
  scanf("%d", &n);
  memset(dp, 0, sizeof(int) * (n + 1));
  for (int i = 1; i <= n; i++) scanf("%d", cars + i);
  for (int i = 1; i <= n; i++) dp[cars[i]] = dp[cars[i] - 1] + 1;
  for (int i = 1; i <= n; i++) dp[0] = ((dp[0]) > (dp[i]) ? (dp[0]) : (dp[i]));
  printf("%d\n", n - dp[0]);
}
