// LIS を使った WA 解
#include <bits/stdc++.h>
using namespace std;

int solve() {
  int n;
  cin >> n;
  vector<int> A(n);
  for (int i = 0; i < n; i++) cin >> A[i];

  // LIS の長さを求めています
  const int inf = 1e9;
  vector<int> dp(n, inf);
  for (int i = 0; i < n; i++) *lower_bound(dp.begin(), dp.end(), A[i]) = A[i];
  int lis = lower_bound(dp.begin(), dp.end(), inf) - dp.begin();

  return n - lis;
}

int main() {
  cin.tie(nullptr); ios::sync_with_stdio(false);
  cout << solve() << endl;
  return 0;
}