Untitled

#include<bits/stdc++.h>
using namespace std;
#define IOS ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ll long long
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

#define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update>
#define endl "\n"
const ll mod = 1e9+7;
#define fi first
#define ss second
using ii = pair<ll,ll>;
#define pb push_back
#define mp make_pair
#define sz(x) (ll)(x).size()
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
#define ins insert
#define vll vector<ll>
#define vvll vector<vll>
ll const N = 200100;
ll power(ll x,ll y,ll modd){ll res = 1;while(y){if(y&1) res = (res*x)%modd;y=y/2,x=(x*x)%modd;}return res%modd;}

class Solution {
public:
    long long minMaxSubarraySum(vector<int>& nums, int k) {
        ll n = sz(nums);
        deque<ii>q;
        ll ans = 0;
        ll csum = 0;
        //ll ans=0;
        ll i = n-1;
        ll j = n-1;
        while(i>=0){
            while(j-i>=k){
                ii las = q.front();
                q.pop_front();
                csum-= las.fi;
                if(las.ss>1){
                    q.push_front(mp(las.fi,las.ss-1));
                }
                j--;
            }
            ll ta = 1;
            while(!q.empty() and q.back().fi < nums[i]){
                ta+= q.back().ss;
                csum-= (q.back().ss * q.back().fi);
                q.pop_back();
            }
            csum+= ta*nums[i];
            q.push_back(mp(nums[i],ta));
            ans+= csum;
            i--;
        }
        deque<ii>q1;
        csum=0;
        i = n-1;
        j = n-1;
        while(i>=0){
            while(j-i>=k){
                ii las = q1.front();
                q1.pop_front();
                csum-= las.fi;
                if(las.ss>1){
                    q1.push_front(mp(las.fi,las.ss-1));
                }
                j--;
            }
            ll ta = 1;
            while(!q1.empty() and q1.back().fi > nums[i]){
                ta+= q1.back().ss;
                csum-= (q1.back().ss * q1.back().fi);
                q1.pop_back();
            }
            csum+= ta*nums[i];
            q1.push_back(mp(nums[i],ta));
            ans+= csum;
            i--;
        }
        return ans;
    }
};©leetcode