#include <bits/stdc++.h>
int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
int lcm(int a, int b) { return ((a * b) / gcd(a, b)); }
using namespace std;
int lol[100005];
int main() {
  int a, b, c, i, j, k, tc, t;
  int n, m, cnt = 0;
  int ara[100005], ara1[100005];
  cin >> n;
  for (i = 0; i < n; i++) {
    scanf("%d", &ara[i]);
    ara1[ara[i]] = i + 1;
  }
  lol[1] = 1;
  int Max = 1;
  for (i = 2; i <= n; i++) {
    if (ara1[i] > ara1[i - 1])
      lol[i] = lol[i - 1] + 1;
    else
      lol[i] = 1;
    Max = max(Max, lol[i]);
  }
  printf("%d\n", n - Max);
  return 0;
}
