#include<bits/stdc++.h>

using namespace std;
const int N=1000100;

int a[N];
vector<int>pos[N];
vector<array<int,2>> seg,seg1;
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){
			seg.push_back({i,pos[x][k-1]});
			pos[x].erase(pos[x].begin());
		}
		
	}
	int lst=0;
	long long ans=0;
	sort(seg.begin(),seg.end());
	reverse(seg.begin(),seg.end());
	for(int i=0;i<seg.size();i++){

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

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

}