D 95% 求 hack

#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,a,n) for(int i=n;i>=a;i--)
#define endl "\n"
#define pb push_back
#define be begin()
#define ed end()
#define fi first
#define se second
#define ls i<<1
#define rs i<<1|1
using ll=long long;
using pii=pair<int,int>;
using pll=pair<ll,ll>;
using ull=unsigned long long;
int n,k;
#define N 200010
int a[N],b[N];
struct node{
	int l,r,k;
};
vector<node> vec[N];
vector<int> c[N];
int t[N<<2],mx[N<<2],lz[N<<2];
void pu(int i){
	if(mx[ls]==mx[rs]) mx[i]=mx[ls],t[i]=t[ls]+t[rs];
	else if(mx[ls]>mx[rs]) mx[i]=mx[ls],t[i]=t[ls];
	else mx[i]=mx[rs],t[i]=t[rs];
}
void build(int i,int l,int r){
	mx[i]=0,lz[i]=0;
	if(l==r){
		t[i]=1;return;
	}
	int mid=(l+r)>>1;
	build(ls,l,mid);
	build(rs,mid+1,r);
	pu(i);
}
void pd(int i){
	if(lz[i]){
		mx[ls]+=lz[i],lz[ls]+=lz[i];
		mx[rs]+=lz[i],lz[rs]+=lz[i];
		lz[i]=0;
	}
}
void ch(int i,int l,int r,int cl,int cr,int k){
	if(l>cr||r<cl) return;
	if(l>=cl&&r<=cr){
		mx[i]+=k,lz[i]+=k;
		return;
	}
	int mid=(l+r)>>1;
	pd(i);
	ch(ls,l,mid,cl,cr,k),ch(rs,mid+1,r,cl,cr,k);
	pu(i);
}
pii que(int i,int l,int r,int cl,int cr){
	if(l>cr||r<cl) return (pii){0,0};
	if(l>=cl&&r<=cr) return (pii){mx[i],t[i]};
	pd(i);
	int mid=(l+r)>>1;
	auto [mxls,numls]=que(ls,l,mid,cl,cr);
	auto [mxrs,numrs]=que(rs,mid+1,r,cl,cr);
	int mx1,ans;
	if(mxls==mxrs) mx1=mxls,ans=numls+numrs;
	else if(mxls>mxrs) mx1=mxls,ans=numls;
	else mx1=mxrs,ans=numrs;
	pu(i);
	return (pii){mx1,ans};
}
void solve(){
	rep(i,1,n) c[i].clear(),vec[i].clear();
	cin>>n>>k;
	rep(i,1,n) cin>>a[i],b[i]=a[i];
	sort(b+1,b+n+1);
	int tot=unique(b+1,b+n+1)-b-1;
	rep(i,1,n) c[i].pb(0);
	rep(i,1,n){
		a[i]=lower_bound(b+1,b+tot+1,a[i])-b;
		c[a[i]].pb(i);		
	}
	int m=0;
	rep(i,1,n){
		if(c[i].size()==1) continue;
		c[i].pb(n+1);
		m++;
		rep(j,k,(int)c[i].size()-2){
			vec[c[i][j]].pb({c[i][j-k]+1,c[i][j-k+1],1});
			vec[c[i][j+1]].pb({c[i][j-k]+1,c[i][j-k+1],-1});
		}
		rep(j,1,(int)c[i].size()-1){
			int l=c[i][j-1]+1,r=c[i][j]-1;
			if(l<=r){
				vec[l].pb({l,r,1});
				vec[r+1].pb({l,r,-1});
			}
		}
	}
	build(1,1,n);
	ll ans=0;
	rep(i,1,n){
		for(auto [l,r,v]:vec[i]){
			ch(1,1,n,l,r,v);
		}
		auto [mx1,num]=que(1,1,n,1,i);
		if(mx1==m) ans+=num;
	}
	cout<<ans<<endl;
}
int main(){
	IOS
	int t=1; cin>>t;
	while(t--) solve();
	return 0;
}