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