Shared code

#include <algorithm>
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3")
#define int long long 
const int N = 5e6 + 10, M = 22;
const int inf = 1e15 + 10;

template <typename num_t> 
struct segtree {
  int n, depth;
  vector<num_t> tree, lazy;

  void init(int s, long long* arr) {
    n = s;
    tree = vector<num_t>(4 * s, 0);
    lazy = vector<num_t>(4 * s, 0);
    init(0, 0, n - 1, arr);
  }

  num_t init(int i, int l, int r, long long* arr) {
    if (l == r) return tree[i] = arr[l];

    int mid = (l + r) / 2;
    num_t a = init(2 * i + 1, l, mid, arr),
          b = init(2 * i + 2, mid + 1, r, arr);
    return tree[i] = a.op(b);
  }

  void update(int l, int r, num_t v) {
	if (l > r) return;
    update(0, 0, n - 1, l, r, v);
  }

  num_t update(int i, int tl, int tr, int ql, int qr, num_t v) {
    eval_lazy(i, tl, tr);
	
	if (tr < ql || qr < tl) return tree[i];
    if (ql <= tl && tr <= qr) {
      lazy[i] = lazy[i].val + v.val;
      eval_lazy(i, tl, tr);
      return tree[i];
    }
    
    int mid = (tl + tr) / 2;
    num_t a = update(2 * i + 1, tl, mid, ql, qr, v),
          b = update(2 * i + 2, mid + 1, tr, ql, qr, v);
    return tree[i] = a.op(b);
  }

  num_t query(int l, int r) {
	if (l > r) return num_t::null_v;
    return query(0, 0, n-1, l, r);
  }

  num_t query(int i, int tl, int tr, int ql, int qr) {
    eval_lazy(i, tl, tr);
    
    if (ql <= tl && tr <= qr) return tree[i];
    if (tr < ql || qr < tl) return num_t::null_v;

    int mid = (tl + tr) / 2;
    num_t a = query(2 * i + 1, tl, mid, ql, qr),
          b = query(2 * i + 2, mid + 1, tr, ql, qr);
    return a.op(b);
  }

  void eval_lazy(int i, int l, int r) {
    tree[i] = tree[i].lazy_op(lazy[i], (r - l + 1));
    if (l != r) {
      lazy[i * 2 + 1] = lazy[i].val + lazy[i * 2 + 1].val;
      lazy[i * 2 + 2] = lazy[i].val + lazy[i * 2 + 2].val;
    }

    lazy[i] = num_t();
  }
};

struct max_t {
  long long val;
  static const long long null_v = -9223372036854775807LL;

  max_t(): val(0) {}
  max_t(long long v): val(v) {}

  max_t op(max_t& other) {
    return max_t(max(val, other.val));
  }
  
  max_t lazy_op(max_t& v, int size) {
    return max_t(val + v.val);
  }
};

inline void solve(){
    int n;
    cin >> n;

    vector<int> v(n);
    for(auto &x : v) cin >> x;

    vector<pair<int,int>> a;
    for(int i = 0;i < n;i += 1){
        a.push_back({v[i], i});
    }

    sort(a.begin(), a.end());

    vector<int> l(n), r(n);

    {
        stack<int> st;
        for(int i = 0;i < n;i += 1){
            while(!st.empty() && v[i] > v[st.top()]){
                st.pop();
            }
            l[i] = (st.empty() ? -1 : st.top());
            st.push(i);
        }
    }

    {
        stack<int> st;
        for(int i = n - 1;i >= 0;i -= 1){
            while(!st.empty() && v[i] > v[st.top()]){
                st.pop();
            }
            r[i] = (st.empty() ? n : st.top());
            st.push(i);
        }
    }

    // for(int i = 0;i < n;i += 1){
    //     cout << l[i] << ' ' << r[i] << '\n';
    // }
    
    vector<int> dp(n);

    segtree<max_t> sgt;
    sgt.init(n, dp.data());

    for(int i = 0;i < n;i += 1){
        int ind = a[i].second;
        int ll = l[ind], rr = r[ind];

        dp[ind] = sgt.query(ll + 1, rr - 1).val + 1;
        sgt.update(ind,ind, dp[ind]);
    }

    // for(auto &x : dp) cout << x << ' ';
    // cout << '\n';

    cout << *max_element(dp.begin(), dp.end());

    
    
}

int32_t main() {

    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t = 1;
    // cin >> t;

    while(t--){
        solve();
        cout << "\n";
    }
}