#include <bits/stdc++.h>
using namespace std;
long long int powmod(long long int a, long long int b) {
  if (b == 0) return 1;
  long long int x = powmod(a, b / 2);
  long long int y = (x * x) % 1000000007;
  if (b % 2) return (a * y) % 1000000007;
  return y % 1000000007;
}
int cnt[100010], pos[100010];
int main() {
  int n;
  scanf("%d", &n);
  for (int i = 0; i < n; i++) {
    int x;
    scanf("%d", &x);
    pos[x] = i;
    cnt[x] = 1;
  }
  int ma = 1;
  for (int i = 1; i < 100002; i++) {
    if (pos[i] > pos[i - 1]) cnt[i] += cnt[i - 1];
    ma = max(cnt[i], ma);
  }
  printf("%d\n", n - ma);
  return 0;
}
