#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
using namespace std;
#define mk make_pair
#define MID int mid=(l+r)>>1;
#define ll long long
#define ls p<<1
#define rs p<<1|1
#define endl '\n'
#define siz(a) int(a.size())
int n,k,a[1000100],pos[1000100],num[1000100<<2],mi[1000100<<2],la[1000100<<2];
ll ans;
vector<int>g[1000100];
void up(int p){
	if(mi[ls]==mi[rs]){
		num[p]=num[ls]+num[rs];
	}
	if(mi[ls]>mi[rs]){
		num[p]=num[rs];
	}
	if(mi[ls]<mi[rs]){
		num[p]=num[ls];
	}
}
void build(int l,int r,int p){
	if(l==r){
		num[p]=1;
		mi[p]=0;return;
	}
	MID;
	build(l,mid,ls),build(mid+1,r,rs);
	up(p);
}
void add(int p,int val){
	mi[p]+=val;
	la[p]+=val;
}
void down(int p){
	if(la[p]){
		add(ls,la[p]);
		add(rs,la[p]);
		la[p]=0;
	}
}

void add(int l,int r,int lin,int rin,int p,int val){
	// cout<<lin<<' '<<rin<<endl;
	if(lin>rin)swap(lin,rin);
	if(l==lin&&r==rin){
		add(p,val);
		return;
	}
	down(p);
	MID;
	if(rin<=mid)add(l,mid,lin,rin,ls,val);
	else if(lin>mid)add(mid+1,r,lin,rin,rs,val);
	else add(l,mid,lin,mid,ls,val),add(mid+1,r,mid+1,rin,rs,val);
	up(p);
}
void pr(int l,int r,int lin,int rin,int p){
	if(lin>rin)swap(lin,rin);
	if(l==lin&&r==rin){
		if(mi[p]==0)ans+=num[p];
		return;	
	}
	down(p);
	MID;
	if(rin<=mid)pr(l,mid,lin,rin,ls);
	else if(lin>mid)pr(mid+1,r,lin,rin,rs);
	else pr(l,mid,lin,mid,ls),pr(mid+1,r,mid+1,rin,rs);
}
void solve(){
	cin>>n>>k;
	build(1,n,1);
	for(int i=1;i<=n;i++)g[i].push_back(0);
	for(int i=1;i<=n;i++)cin>>a[i],g[a[i]].push_back(i),pos[i]=g[a[i]].size()-1;
	for(int i=1;i<=n;i++){
		if(pos[i]>=k){
			if(pos[i]>=k+1){
				add(1,n,g[a[i]][pos[i]-k-1]+1,g[a[i]][pos[i]-k],1,-1);
			}
			add(1,n,g[a[i]][pos[i]-k]+1,g[a[i]][pos[i]-k+1],1,+1);
		}
		pr(1,n,1,i,1);
	}
	cout<<ans;
}
int main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	int TTT;
	// cin>>TTT;
	TTT=1;
	while(TTT--)solve();	
}