#include <bits/stdc++.h>

using namespace std;

const int INF = 1 << 30;

int main() {
  int N, A[200000];
  cin >> N;
  for(int i = 0; i < N; i++) {
    cin >> A[i];
  }
  vector< int > lis(N, INF);
  for(int i = 0; i < N; i++) {
    *lower_bound(begin(lis), end(lis), A[i]) = A[i];
  }
  int sz = lower_bound(begin(lis), end(lis), INF) - begin(lis);

  cout << N - sz << endl;
}