#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <sstream>
#include <map>
#include <set>

#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1<<30
#define pb push_back
#define mp make_pair

using namespace std;
typedef long long ll;
typedef pair<int,int> P;

int LIS(vector<int> v) {
  vector<int> ret(v.size() + 1);
  rep(i, v.size()+1) ret[i] = INF;
  rep(i, v.size()) {
      *lower_bound(ret.begin(), ret.end(), v[i]) = v[i];
  }

  return lower_bound(ret.begin(), ret.end(), INF) - ret.begin();
}

int main() {
  int n;
  cin >> n;

  vector<int> v(n);
  rep(i, n) cin >> v[i];

  cout << n - LIS(v) << endl;

  return 0;
}