Shared code

#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>

using namespace std;

class SegmentTree{
    private:
    vector<int> seg;
    vector<int> arr;
    public:
    SegmentTree(int n){
        seg.resize(4*n, 0);
        arr.resize(n, 0);
    }
    int query(int ind, int low, int high, int l, int h){
        if(high < l || h < low) return 0;
        if(l <= low && high <= h) return seg[ind];

        int mid = low + (high - low)/2;
        int left = query(2*ind+1, low, mid, l, h);
        int right = query(2*ind+2, mid+1, high, l, h);
        return max(left, right);
    }
    void update(int ind, int low, int high, int i, int val){
        if(low == high){
            seg[ind] = val;
            return;
        }
        int mid = low + (high - low)/2;
        if(i <= mid){
            update(2*ind + 1, low, mid, i, val);
        }
        else{
            update(2*ind+2, mid+1, high, i, val);
        }
        seg[ind] = max(seg[2*ind + 1], seg[2*ind + 2]);
    }
};

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int n;
    if(!(cin >> n)) return 0;
    if(n == 1){
        cout << 1 << '\n';
        return 0;
    }
    vector<int> hills(n);
    if(n == 1){
        cout << 0 << '\n';
        return 0;
    }
    for(int i=0; i<n; i++) cin >> hills[i];
    
    vector<int> L(n), R(n);
    stack<int> st;

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

    while(!st.empty()) st.pop();

    for(int i=n-1; i>=0; i--){
        while(!st.empty() && hills[st.top()] < hills[i]) st.pop();
        R[i] = (st.empty() ? n : st.top());
        st.push(i);
    }
    
    vector<int> h(n);
    for(int i=0; i<n; i++) h[i] = i;
    sort(h.begin(), h.end(), [&](int a, int b){
                                return hills[a] < hills[b];});
    
    SegmentTree segTree(n);
    vector<int> dp(n, 0);
    int maxRange = 0;
    for(int i: h){
        int left = segTree.query(0, 0, n-1, L[i]+1, i-1);
        int right = segTree.query(0, 0, n-1, i+1, R[i]-1);
        dp[i] =  1 + max(left, right);
        segTree.update(0, 0, n-1, i, dp[i]);
        maxRange = max(maxRange, dp[i]);
    }

    cout << maxRange << '\n';
    return 0;

}