Sum of max and min in all subarrays

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define pb push_back
#define mp make_pair
#define vpll vector<pair<ll,ll>>
#define vll vector<ll>
#define mpll map<ll,ll>
#define all(x) x.begin(),x.end()
#define sortall(x) sort(x.begin(),x.end())
#define line cout<<'\n'
#define fo(i,n) for(int i=0;i<n;i++)
#define foe(i,a,n) for(int i=a;i<n;i++)
#define fr(i,n) for(int i=n-1;i>=0;i--)
#define cy cout<<"YES"<<endl
#define cn cout<<"NO"<<endl
#define debug(x) cout<<x<<endl
#define print(x) cout<<x<<" "
#define deb(x,y) cout<<x<<" "<<y<<endl
#define MOD 1000000007
const int N1=100001;
bool isPrime[N1];
void sieve()
{
    memset(isPrime, true, sizeof(isPrime));
    for (int p = 2; p * p <= N1; p++)
    {
        if (isPrime[p] == true)
        {
            for (int i = p * p; i <= N1; i += p)
                isPrime[i] = false;
        }
    }
}
long long power(long long a, long long b) {
    if (b == 0)
        return 1;
    long long res = power(a, b / 2);
    if (b % 2)
        return res * res * a;
    else
        return res * res;
}
/*====================================================================================*/

int sumMaxMin(vector<int> &a,int k)
{
    deque<int> dqmin,dqmax;
    int n=a.size();
    int ans=0;
    for(int i=0;i<k;i++)
    {
        //first window
        //remove the elements which cant be the candidate
        while(!dqmin.empty() and a[dqmin.back()]>=a[i]) dqmin.pop_back();
        while(!dqmax.empty() and a[dqmax.back()]<=a[i]) dqmax.pop_back();
        dqmin.push_back(i);
        dqmax.push_back(i);
    }
    // print(a[dqmax.front()]); print(a[dqmin.front()]);
    ans+=a[dqmin.front()]+a[dqmax.front()];
    for(int i=k;i<n;i++)
    {
        //remove out of window elements
        while(!dqmin.empty() and dqmin.front()<i-k+1) dqmin.pop_front();
        while(!dqmax.empty() and dqmax.front()<i-k+1) dqmax.pop_front();

        //remove the elements which cant be the candidate
        while(!dqmin.empty() and a[dqmin.back()]>=a[i]) dqmin.pop_back();
        while(!dqmax.empty() and a[dqmax.back()]<=a[i]) dqmax.pop_back();
        dqmin.push_back(i);
        dqmax.push_back(i);
        // print(a[dqmax.front()]); print(a[dqmin.front()]);
        ans+=a[dqmin.front()]+a[dqmax.front()];
    }
    return ans;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll t=1;
    cin>>t;

    while(t--)
    {
        int n,k; cin>>n>>k;
        vector<int> a(n);
        for(int i=0;i<n;i++) cin>>a[i];
        cout<<sumMaxMin(a,k);
    }
}