LIS_BIT.cpp

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

void chmax(int &a, int b) {
  if (a < b) a = b;
}

struct BIT {
  int n; vector<int> bit;
  BIT(int n): n(n), bit(n + 1) {}
  void update(int i, int v) {
    for (; i <= n; i += i & -i) {
      chmax(bit[i], v);
    }
  }
  int get(int i) {
    int v = 0;
    for (; i; i -= i & -i) {
      chmax(v, bit[i]);
    }
    return v;
  }
};

signed main() {
  cin.tie(0)->sync_with_stdio(0);
  int n; cin >> n;
  vector<int> a(n), v(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
    v[i] = a[i];
  }
  sort(v.begin(), v.end());
  v.resize(unique(v.begin(), v.end()) - v.begin());
  for (auto &i : a) {
    i = v.end() - lower_bound(v.begin(), v.end(), i);
  }
  int ans = 0;
  BIT bit(n);
  for (auto &i : a) {
    int t = bit.get(i);
    chmax(ans, t + 1);
    bit.update(i, t + 1);
  }
  cout << ans << '\n';
}