#include <bits/stdc++.h>
using namespace std;
int dp[1123456], p[1123456];
int main() {
  int n, i, j;
  scanf("%d", &n);
  for (i = 0; i < n; ++i) {
    scanf("%d", &j);
    p[j] = i;
  }
  dp[1] = 1;
  int ans = 1;
  for (i = 2; i <= n; ++i) {
    if (p[i] > p[i - 1]) {
      dp[i] = 1 + dp[i - 1];
    } else {
      dp[i] = 1;
    }
    ans = max(ans, dp[i]);
  }
  cout << n - ans << endl;
  return 0;
}
