#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define MP make_pair
mt19937 rnd(time(0));
const int MAXN=1e6+5;
int n,k,a[MAXN];
int nxt[MAXN],lst[MAXN],cnt[MAXN],pre[MAXN],las[MAXN],rnk[MAXN],now[MAXN];
struct segt{
int minn[MAXN<<2],laz[MAXN<<2],cnt[MAXN<<2];
void push(int id,int d){
	minn[id]+=d;laz[id]+=d;
}
void pushdown(int id){
	push(id<<1,laz[id]);push(id<<1|1,laz[id]);
}
void pushup(int id){
	minn[id]=min(minn[id<<1],minn[id<<1|1]);cnt[id]=0;
	if(minn[id]==minn[id<<1]) cnt[id]+=cnt[id<<1];
	if(minn[id]==minn[id<<1|1]) cnt[id]+=cnt[id<<1|1];
}
void add(int L,int R,int d,int id=1,int l=1,int r=n){
	if(L<=l&&r<=R){
		push(id,d);
		return;
	}
	int mid=l+r>>1;
	pushdown(id);
	if(L<=mid) add(L,R,d,id<<1,l,mid);
	if(mid<R) add(L,R,d,id<<1|1,mid+1,r);
	pushup(id);
}
int ask(int L,int R,int id=1,int l=1,int r=n){
	if(L<=l&&r<=R) return minn[id]==0?cnt[id]:0;
	int mid=l+r>>1;
	pushdown(id);
	if(R<=mid) return ask(L,R,id<<1,l,mid);
	if(mid<L) return ask(L,R,id<<1|1,mid+1,r);
	return ask(L,R,id<<1,l,mid)+ask(L,R,id<<1|1,mid+1,r);
}
void build(int id=1,int l=1,int r=n){
	cnt[id]=r-l+1;
	if(l==r) return;
	int mid=l+r>>1;
	build(id<<1,l,mid);build(id<<1|1,mid+1,r);
} 
}T;
int main(){
	ios::sync_with_stdio(false);
	cin>>n>>k;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=n;i>=1;i--){
		nxt[i]=lst[a[i]];lst[a[i]]=i;
	}
	for(int i=1;i<=n;i++){
		rnk[i]=++cnt[a[i]];pre[i]=las[a[i]];las[a[i]]=i;
	}
	ll ans=0;
	T.build();
	for(int i=1;i<=n;i++){
		if(rnk[i]==k) now[a[i]]=lst[a[i]];
		else if(rnk[i]>k){
			T.add(pre[now[a[i]]]+1,now[a[i]],-1);
			now[a[i]]=nxt[now[a[i]]];
		} 
		if(now[a[i]]) T.add(pre[now[a[i]]]+1,now[a[i]],1);
		ans+=T.ask(1,i);
	}
	cout<<ans<<endl;
	return 0;
}