#include <bits/stdc++.h>
using namespace std;
using lint = long long;
const int INF = 1e9;

signed main(){
  int n; cin >> n;
  vector<int> a(n), dp(n, INF);
  for(int i = 0; i < n; i++) scanf("%d", &a[i]);
  for(int i = 0; i < n; i++){
    *lower_bound(dp.begin(), dp.end(), a[i]) = a[i];
  }
  cout << n - (lower_bound(dp.begin(), dp.end(), INF) - dp.begin()) << endl;
}