#include <bits/stdc++.h>
using namespace std;
set<int> my_set;
set<int>::iterator it;
vector<int> out;
int main() {
  int n;
  cin >> n;
  for (int i = 1; i <= n; i++) {
    int x;
    cin >> x;
    it = my_set.find(x);
    if (it != my_set.end() && *it == x) {
      continue;
    }
    my_set.insert(x);
    it = my_set.find(x);
    it++;
    if (it != my_set.end())
      my_set.erase(it);
    else
      out.push_back(*it);
  }
  cout << endl << out.size();
}
