1849E - Max to the Right of Min - CodeForces Solution

#include<bits/stdc++.h>
using namespace std;
int main()
{
    // freopen("test.in","r",stdin);
    // freopen("test.out","w",stdout);
    int n;
    cin>>n;
    vector<int>ar(n);
    for(int i = 0;i < n;i ++)
        cin>>ar[i];
    vector<int>lmin(n,-1),rmin(n,n),lmax(n,-1),rmax(n,n);
    vector<int>stk;
    for(int i = 0;i < n;i ++)
    {
        while(stk.size() && ar[stk.back()] < ar[i])
        {
            rmax[stk.back()] = i;
            stk.pop_back();
        }
        if(stk.size())
            lmax[i] = stk.back();
        stk.push_back(i);
    }
    stk.clear();
    for(int i = 0;i < n;i ++)
    {
        while(stk.size() && ar[stk.back()] > ar[i])
        {
            rmin[stk.back()] = i;
            stk.pop_back();
        }
        if(stk.size())
            lmin[i] = stk.back();
        stk.push_back(i);
    }
    stk.clear();
    vector<long long>sum;
    sum.push_back(0LL);
    long long ans = 0;
    for(int i = 0;i < n;i ++)
    {
        while(stk.size() && ar[stk.back()] > ar[i])
        {
            stk.pop_back();
            sum.pop_back();
        }
        int id = upper_bound(stk.begin(),stk.end(),lmax[i]) - stk.begin();
        if(id < stk.size())
        {
            ans += 1LL * (stk[id] - max(lmin[stk[id]],lmax[i])) * (min(rmin[stk[id]],rmax[i]) - i);
            id ++;
            auto r = partition_point(stk.begin() + id,stk.end(),[&](int x){
                return rmin[x] > rmax[i];
            }) - stk.begin();
            if(id < r)
                ans += 1LL * (stk[r - 1] - lmin[stk[id]]) * rmax[i];
            // for(int j = r;j < stk.size();j ++)
                // ans += (stk[j] - lmin[stk[j]]) * rmin[stk[j]];
            if(r < stk.size())
                ans += sum.back() - sum[r];
            if(id < stk.size())
                ans -= 1LL * (stk.back() - lmin[stk[id]]) * i;
        }
        sum.push_back(sum.back() + 1LL * (i - lmin[i]) * rmin[i]);
        stk.push_back(i);
    }
    cout<<ans<<"\n";
}