#include<bits/stdc++.h>

using namespace std;
const int N=1000100;

int a[N];
vector<int>pos[N];
vector<array<int,3>> seg,seg1,seg2;
queue<int>q;
int c[N];
void modify(int x,int d){
	for(;x<=N;x+=x&-x) c[x]+=d;
}
int query(int x){
	int s=0;
	for(;x;x-=x&-x) s+=c[x];
	return s;
}
int main(){

	int n,k;
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++){ 
		scanf("%d",&a[i]);
		pos[a[i]].push_back(i);
	}
	for(int i=1;i<=n;i++){
		int x=a[i];
		if(pos[x].size()>=k){
			
			if(pos[x].size()>k){
				seg.push_back({i,pos[x][k-1],pos[x][k]});
			}
			else
				seg2.push_back({i,pos[x][k-1],n});
			pos[x].erase(pos[x].begin());
		}
		
	}
	int lst=0;
	long long ans=0;
	sort(seg2.begin(),seg2.end());
	reverse(seg2.begin(),seg2.end());
	for(int i=0;i<seg2.size();i++){

		if(query(seg2[i][1])==0)
			seg1.push_back({seg2[i][0],seg2[i][1],seg2[i][2]});
		modify(seg2[i][1],1);

	}
	sort(seg1.begin(),seg1.end());
	for(auto [x,y,z]:seg1){
	//	cout<<x<<" "<<y<<endl;
		ans=ans+1ll*(x-lst)*(z-y+1);
		lst=x;
	}
	printf("%lld\n",1ll*n*(n-1)/2+n-ans);

}