#include <bits/stdc++.h>
using namespace std;
bool isprime(long long n) {
  for (long long i = 2; i <= sqrt(n); i++) {
    if (n % i == 0) return false;
  }
  return true;
}
bool prm[10000007];
long long N = 10000000;
void sieve() {
  prm[1] = 1;
  for (long long i = 2; i <= sqrt(N); i++) {
    if (prm[i] == 0) {
      for (long long j = i + i; j <= N; j = j + i) prm[j] = 1;
    }
  }
}
long long bm(long long b, long long p) {
  long long namira;
  if (p == 0) return 1;
  if (p % 2 == 0) {
    namira = bm(b, p / 2);
    return ((namira % 1000000007) * (namira % 1000000007)) % 1000000007;
  } else {
    return ((b % 1000000007) * (bm(b, p - 1) % 1000000007)) % 1000000007;
  }
}
long long arr[200010];
long long a[200010];
long long tree1[200010 * 3];
void init(long long node, long long b, long long e) {
  if (b == e) {
    tree1[node] = 1;
    return;
  }
  long long Left = node * 2;
  long long Right = node * 2 + 1;
  long long mid = (b + e) / 2;
  init(Left, b, mid);
  init(Right, mid + 1, e);
  tree1[node] = tree1[Left] + tree1[Right];
}
long long query(long long node, long long b, long long e, long long i) {
  if (a[b] > i) return 0;
  if (a[e] <= i) {
    return tree1[node];
  }
  long long Left = node * 2;
  long long Right = node * 2 + 1;
  long long mid = (b + e) / 2;
  long long p1 = query(Left, b, mid, i);
  long long p2 = query(Right, mid + 1, e, i);
  return p1 + p2;
}
void update(long long node, long long b, long long e, long long i,
            long long newvalue) {
  if (i > e || i < b) return;
  if (b >= i && e <= i) {
    tree1[node] = newvalue;
    return;
  }
  long long Left = node * 2;
  long long Right = node * 2 + 1;
  long long mid = (b + e) / 2;
  update(Left, b, mid, i, newvalue);
  update(Right, mid + 1, e, i, newvalue);
  tree1[node] = tree1[Left] + tree1[Right];
}
int main() {
  long long a[100010], b[100010], n, i, r, c;
  scanf("%I64d", &n);
  for (i = 1; i <= n; i++) {
    scanf("%I64d", &a[i]);
    b[i] = 0;
  }
  b[0] = 0;
  b[n + 1] = 0;
  for (i = n; i >= 1; i--) {
    b[a[i]] = 1;
    b[a[i]] = b[a[i]] + b[a[i] + 1];
  }
  r = n - (*max_element(b, b + n + 1));
  printf("%I64d\n", r);
  return 0;
}
