Shared code

#include <bits/stdc++.h>
using namespace std;
 
template <typename T> class SegmentTree {
public:
  int _n, n;
  T idt;
  std::vector<T> seg;
  std::function<T(T, T)> f;
 
  static int bit_ceil(int n) {
    int m = 1;
    while (m < n)
      m *= 2;
    return m;
  }
  SegmentTree(int _n, std::function<T(T, T)> f = std::plus<T>(), T idt = T())
      : _n(_n), n(bit_ceil(uint32_t(_n))), idt(idt), seg(2 * n, idt), f(f) {}
 
  void set(int idx, T x) {
    for (seg[idx += n] = x, idx /= 2; idx > 0; idx /= 2) {
      seg[idx] = f(seg[2 * idx], seg[2 * idx + 1]);
    }
  }
 
  T query(int l, int r) {
    T ansL = idt, ansR = idt;
    for (l += n, r += n + 1; l < r; l /= 2, r /= 2) {
      if (l & 1) ansL = f(ansL, seg[l++]);
      if (r & 1) ansR = f(seg[--r], ansR);
    }
    return f(ansL, ansR);
  }
 
  int partition_point(int l, const std::function<bool(T)> &t) {
    T p = idt;
    for (l += n; t(f(p, seg[l])) and (l & (l + 1)); l /= 2) {
      if (l & 1)
        p = f(p, seg[l++]);
    }
    if (t(f(p, seg[l]))) {
      return _n;
    }
    while (l < n) {
      if (t(f(p, seg[l <<= 1])))
        p = f(p, seg[l++]);
    }
    return l - n;
  }
};
 
int main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(nullptr);
 
  const int inf = 1e9;
 
  int n;
  std::cin >> n;
  std::vector<int> a(n);
  std::vector<std::pair<int, int>> p(n);
  for (int i = 0; i < n; ++i) {
    std::cin >> a[i];
    p[i].first = a[i], p[i].second = i;
  }
  std::sort(p.begin(), p.end());
 
  auto get_next = [&](const std::vector<int> &a) {
    SegmentTree<int> st(n, [](int a, int b) {
      return std::max(a, b);
    }, -inf);
    for (int i = 0; i < n; ++i) {
      st.set(i, a[i]);
    }
    std::vector<int> ans(n);
    for (int i = 0; i < n; ++i) {
      ans[i] = st.partition_point(i + 1, [&](int x) {
        return x < a[i];
      }) - 1;
    }
    return ans;
  };
  auto right = get_next(a);
  std::reverse(a.begin(), a.end());
  auto left = get_next(a);
  std::reverse(left.begin(), left.end());
  for (int i = 0; i < n; ++i) {
    left[i] = n - left[i] - 1;
  }
 
  SegmentTree<int> dp(n, [](int a, int b) {
    return std::max(a, b);
  }, -inf);
  for (auto &[v, i] : p) {
    dp.set(i, std::max(dp.query(left[i], right[i]) + 1, 1));
  }
  std::cout << dp.query(0, n - 1) << '\n';
}