#include<cstdio> #include<cstdlib> #include<cstring> #include<string> #include<algorithm> #include<iostream> #include<queue> #include<map> #include<cmath> #include<set> #include<stack> #define ll long long #define pb push_back #define max(x,y) ((x)>(y)?(x):(y)) #define min(x,y) ((x)>(y)?(y):(x)) #define cls(name,x) memset(name,x,sizeof(name))//0或-1 #define fs first #define sc second #define mp make_pair #define L(x) (1<<x) #define next Next using namespace std; const int inf=1e9+10; const ll llinf=1e16+10; const int maxn=5e5+10; const int maxm=2e5+10; const int mod=1e9+7; int n,k; int A[maxn],next[maxn],pre[maxn]; int idx[maxn]; bool cmp(const int &a,const int &b) { return A[a]<A[b]; } void del(int pos) { if(next[pos]!=-1) pre[next[pos]]=pre[pos]; if(pre[pos]!=-1) next[pre[pos]]=next[pos]; } int func(int i,int c[],int op) { if(c[i]==0) return 0; if(op==1) { if(c[i+1]!=0) return c[i] - (c[i+1]+1) + 1; else return c[i] - 1 + 1; } if(op==2) { if(c[i+1]!=0) return (c[i+1]-1) - c[i] + 1; else return n - c[i] + 1; } } ll solve(int pos) { int c1[100],c2[100]; cls(c1,0); cls(c2,0); int t=1; c1[0]=pos; for(int i=pre[pos];i!=-1&&t<=k;i=pre[i]) c1[t++]=i; t=1; c2[0]=pos; for(int i=next[pos];i!=-1&t<=k;i=next[i]) c2[t++]=i; int c=0; for(int i=0;i<=k-1;i++) c+=func(i,c1,1)*func(k-1-i,c2,2); return (ll)c*A[pos]; } int main() { //freopen("in.txt","r",stdin); int ncas; scanf("%d",&ncas); while(ncas--) { scanf("%d %d",&n,&k); for(int i=1;i<=n;i++) { scanf("%d",&A[i]); if(i==1) pre[i]=-1; else pre[i]=i-1; if(i==n) next[i]=-1; else next[i]=i+1; idx[i]=i; } sort(idx+1,idx+n+1,cmp); ll ans=0; for(int i=1;i<=n;i++) { int pos=idx[i]; ans+=solve(pos); del(pos); } printf("%lld ",ans); } return 0; }