#include<bits/stdc++.h>
using namespace std;
int n,k;
int o[1200000];
int pd[1200000];
int ch[1200000];
vector<int>vt[1200000];
long long ans=0;
int zan[1200000],ztop;
int tree[4000000],lazy[4000000];
int tp;
int pushup(int k){
	int RE=0;
	if(!lazy[k<<1])RE+=tree[k<<1];
	if(!lazy[k<<1|1])RE+=tree[k<<1|1];
	return RE;
}
void tree_init(int l,int r,int k,int x,int y){
	if(l>y||r<x){tree[k]=lazy[k]=0;return ;}
	if(l==r){tree[k]=1;lazy[k]=0;return ;}
	int mid=(l+r)>>1;
	tree_init(l,mid,k<<1,x,y);
	tree_init(mid+1,r,k<<1|1,x,y);
	tree[k]=pushup(k);
	lazy[k]=0;
}
void add(int l,int r,int k,int x,int y,int v){
	if(x<=l&&r<=y){lazy[k]+=v;return ;}
	int mid=(l+r)>>1;
	if(x<=mid)add(l,mid,k<<1,x,y,v);
	if(y>mid)add(mid+1,r,k<<1|1,x,y,v);
	tree[k]=pushup(k);
}
void init(int l,int r,int mid){
	r=r;//No Warning "r"
	tree_init(1,n,1,l,mid);
	for(int i=1;i<=ztop;i++){
		if(pd[zan[i]]>=k){
			add(1,n,1,vt[zan[i]][k+1]+1,vt[zan[i]][k],1);
		}
	}
}
void update(int x){
	if(pd[x]){
			if(ch[x]+pd[x]>=k&&ch[x]<=k){
			add(1,n,1,vt[x][k-ch[x]+1]+1,vt[x][k-ch[x]],-1);
		}
		ch[x]++;
		if(ch[x]+pd[x]>=k&&ch[x]<=k){
			add(1,n,1,vt[x][k-ch[x]+1]+1,vt[x][k-ch[x]],1);
		}
		return ;
	}
	else{
		if(ch[x]==k)tp--;
		ch[x]++;
		if(ch[x]==k)tp++;
	}
}
void sol(int l,int r){
	if(l==r){if(k!=1)ans++;return ;}
	if(l+1==r){
		if(o[l]==o[r]){if(k!=1)ans+=2;if(k!=2)ans++;}
		else if(k!=1)ans+=3;return ;
	}
	int mid=(l+r)>>1;
	ztop=0;
	vt[o[mid]].push_back(mid+1);
	vt[o[mid]].push_back(mid);
	pd[o[mid]]++;
	zan[++ztop]=o[mid];ch[o[mid]]=0;
	for(int i=mid-1;i>=l;i--){
		if(!pd[o[i]]){
			vt[o[i]].push_back(mid);
			zan[++ztop]=o[i];
			ch[o[i]]=0;
		}
		pd[o[i]]++;
		vt[o[i]].push_back(i);
	}
	for(int i=1;i<=ztop;i++){
		vt[zan[i]].push_back(l-1);
	}
	init(l,r,mid);
	tp=0;
	for(int i=mid+1;i<=r;i++){
		update(o[i]);
		if(tp)continue;
		ans+=tree[1];
	}
	for(int i=l;i<=r;i++)pd[o[i]]=0,vt[o[i]].clear();
	ztop=0;
	sol(l,mid);sol(mid+1,r);
}
int main(){
	cin>>n>>k;
	for(int i=1;i<=n;i++)scanf("%d",&o[i]);
	sol(1,n);
	cout<<ans<<endl;
}