#include <bits/stdc++.h>
using namespace std;
template <class T>
void initvv(vector<vector<T> > &v, int a, int b, const T &t = T()) {
  v.assign(a, vector<T>(b, t));
}
template <class F, class T>
void convert(const F &f, T &t) {
  stringstream ss;
  ss << f;
  ss >> t;
}
void mainmain() {
  int n;
  cin >> n;
  int m = rand() % 300 + 200;
  vector<int> v;
  for (int(i) = (0); (i) < ((m)); ++(i)) {
    v.push_back(rand() % 1000000000);
  }
  for (int(i) = (0); (i) < ((n)); ++(i)) {
    int x;
    cin >> x;
    v.push_back(x);
  }
  set<pair<int, int> > second;
  second.insert(pair<int, int>(0x3f3f3f3f, 1));
  vector<pair<int, int> > w(n + m, pair<int, int>(-1, -1));
  for (int(i) = (0); (i) < ((n + m)); ++(i)) {
    if (i == m) {
    }
    auto it = second.lower_bound(pair<int, int>(v[i], -i));
    if (*it < pair<int, int>(v[i], -i)) continue;
    if (it != second.begin()) {
      it--;
      w[-it->second] = pair<int, int>(v[i], -i);
      it++;
    }
    if (it->first != 0x3f3f3f3f) {
      second.erase(it);
    }
    second.insert(pair<int, int>(v[i], -i));
  }
  for (int(i) = (0); (i) < ((m)); ++(i)) {
    if (*second.begin() == pair<int, int>(v[i], -i)) {
      second.erase(second.begin());
      continue;
    }
    if (second.find(pair<int, int>(v[i], -i)) != second.end()) {
      cout << v[i] << " " << i << endl;
      for (auto x : second) {
        cout << x.first << " " << -x.second << endl;
      }
      return;
    }
    int p = i;
    while (w[p].first != -1) {
      auto it = second.find(w[p]);
      if (it == second.end()) {
        w[p].first = -1;
        p = -w[p].second;
        continue;
      }
      bool f = (it->second == -199);
      auto it2 = it;
      it2--;
      if (-it2->second < -it->second) {
        w[-it2->second] = *it;
        break;
      }
      w[p].first = -1;
      second.erase(it);
      break;
    }
    continue;
    auto it = second.find(w[i]);
    if (it == second.end()) continue;
    auto it2 = it;
    assert(it2 != second.begin());
    it2--;
    if (it2 != second.begin()) {
      cout << v[i] << " " << i << endl;
      cout << w[i].first << " " << -w[i].second << endl;
      cout << it2->first << " " << -it2->second << endl;
      cout << second.begin()->first << " " << -second.begin()->second << endl;
      for (auto x : second) {
        cout << x.first << " " << -x.second << endl;
      }
      cout << "hoge" << endl;
      return;
    }
    if (-it2->second < -it->second) {
      w[-it2->second] = w[i];
      continue;
    }
    second.erase(it);
  }
  cout << second.size() - 1 << endl;
}
signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout << fixed << setprecision(20);
  mainmain();
}
