#include<bits/stdc++.h>
#define mp make_pair
#define ll long long
#define il inline
using namespace std;
const int maxn=1000010;
const int MAXN=maxn<<2;
il int read(){
	int x=0;
	char c=getchar();
	for(;!(c>='0'&&c<='9');c=getchar());
	for(;c>='0'&&c<='9';c=getchar())
		x=(x<<1)+(x<<3)+c-'0';
	return x;
}
struct info{
	int xl,xr,yl,yr;
}a[maxn];
bool cmp1(info a,info b){return a.xl<b.xl;}
int n,k,m,M,c[maxn];
vector<int>v[maxn];
int dm[MAXN],ds[MAXN],lz[MAXN];
ll ans;
set<pair<int,pair<int,int> > >s;
void update(int i){
	if(dm[i<<1]<dm[i<<1|1])
		dm[i]=dm[i<<1],ds[i]=ds[i<<1];
	else if(dm[i<<1]>dm[i<<1|1])
		dm[i]=dm[i<<1|1],ds[i]=ds[i<<1|1];
	else dm[i]=dm[i<<1],ds[i]=ds[i<<1]+ds[i<<1|1];
}
void pushdown(int i){
	if(lz[i]){
		dm[i<<1]+=lz[i],lz[i<<1]+=lz[i];
		dm[i<<1|1]+=lz[i],lz[i<<1|1]+=lz[i];
	}lz[i]=0;
}
void build(int i,int l,int r){
	if(l==r){
		ds[i]=1;
		return ;
	}int mid=l+r>>1;
	build(i<<1,l,mid);
	build(i<<1|1,mid+1,r);
	update(i);
}
void Add(int i,int l,int r,int L,int R,int x){
//	if(i==1) printf("Add->[%d,%d](%d)\n",L,R,x);
	if(l>=L&&r<=R){
		dm[i]+=x,lz[i]+=x;
		return ;
	}int mid=l+r>>1;
	pushdown(i);
	if(mid>=L) Add(i<<1,l,mid,L,R,x);
	if(mid<R) Add(i<<1|1,mid+1,r,L,R,x);
	update(i);
}
int main(){
	n=read(),k=read();
	for(int i=1;i<=n;i++){
		c[i]=read();
		if(v[c[i]].empty()) v[c[i]].push_back(0);
		v[c[i]].push_back(i),M=max(M,c[i]);
	}
	for(int i=1;i<=M;i++) v[i].push_back(n+1);
	for(int i=1;i<=M;i++)
		for(int j=1;j<(int)v[i].size()-k;j++){
			++m;
			a[m].xl=v[i][j-1]+1,a[m].xr=v[i][j];
			a[m].yl=v[i][j+k-1],a[m].yr=v[i][j+k]-1;
		}
	sort(a+1,a+1+m,cmp1);
	//for(int i=1;i<=m;i++)
//		printf("[%d,%d][%d,%d]\n",a[i].xl,a[i].xr,a[i].yl,a[i].yr);
	ans=1ll*n*(n+1)/2;
	build(1,1,n);
	for(int i=1,j=1;i<=n;i++){
		while(j<=m&&a[j].xl<=i){
			s.insert(mp(a[j].xr,mp(a[j].yl,a[j].yr)));
			Add(1,1,n,a[j].yl,a[j].yr,1),j++;
		}
		while(!s.empty()&&s.begin()->first<i){
			Add(1,1,n,s.begin()->second.first,s.begin()->second.second,-1);
			s.erase(s.begin());
		}
//		printf("%d,%d\n",dm[1],ds[1]);
		if(dm[1]) ans-=n;
		else ans-=n-ds[1];
	}
	printf("%lld\n",ans);
	return 0;
}