#include <bits/stdc++.h>
using namespace std;
int y[100002];
int main() {
  int a, b, c, d, e, i, j, p = -1, q = -1, sum = 0, mx = 0;
  int x[100002];
  cin >> a;
  for (i = 0; i < a; i++) {
    cin >> x[i];
    y[x[i]]++;
    y[x[i]] = y[x[i]] + y[x[i] - 1];
    if (y[x[i]] >= mx) {
      mx = y[x[i]];
      p = (x[i] - y[x[i]]);
      q = (a - x[i]);
    }
  }
  sum = sum + (p + q);
  cout << sum << endl;
  return 0;
}
