#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+100;
int a[N],nx[N],nxk[N],nxk1[N];
vector<int>open[N],close[N];
ll su;
#define ls (n<<1)
#define rs (n<<1|1)
struct tree
{
int mi,nu,lazy;
}
t[N<<2];
void pushdown(int n)
{
if(t[n].lazy)
{
t[ls].lazy+=t[n].lazy;
t[rs].lazy+=t[n].lazy;
t[ls].mi+=t[n].lazy;
t[rs].mi+=t[n].lazy;
t[n].lazy=0;
}
}
void pushup(int n)
{
if(t[ls].mi<t[rs].mi)
{
t[n].mi=t[ls].mi;
t[n].nu=t[ls].nu;
}
else if(t[ls].mi>t[rs].mi)
{
t[n].mi=t[rs].mi;
t[n].nu=t[rs].nu;
}
else
{
t[n].mi=t[ls].mi;
t[n].nu=t[ls].nu+t[rs].nu;
}
}
void create(int n,int l,int r)
{
if(l==r)
{
t[n].mi=0;
t[n].nu=1;
return ;
}
int mi=l+r>>1;
create(ls,l,mi);
create(rs,mi+1,r);
pushup(n);
}
void update(int n,int l,int r,int sl,int sr,int v)
{
if(l>sr||r<sl)
{
return ;
}
if(l>=sl&&r<=sr)
{
t[n].mi+=v;
t[n].lazy+=v;
return ;
}
pushdown(n);
int mi=l+r>>1;
update(ls,l,mi,sl,sr,v);
update(rs,mi+1,r,sl,sr,v);
pushup(n);
}
int answer(int n,int l,int r,int sl,int sr)
{
if(l>sr||r<sl)
{
return 0;
}
if(l>=sl&&r<=sr)
{
if(t[n].mi==0)
return t[n].nu;
else
return 0;
}
pushdown(n);
int mi=l+r>>1;
ll an=0;
an+=answer(ls,l,mi,sl,sr);
an+=answer(rs,mi+1,r,sl,sr);
return an;
}
int main()
{
int n,k;
cin>>n>>k;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
map<int,vector<int>>nu;
for(int i=1;i<=n;i++)
{
nu[a[i]].push_back(i);
if(nu[a[i]].size()>=k)
{
nxk[nu[a[i]][nu[a[i]].size()-k]]=i;
nxk1[nu[a[i]][nu[a[i]].size()-k]]=n+1;
}
if(nu[a[i]].size()>k)
{
nxk1[nu[a[i]][nu[a[i]].size()-k-1]]=i;
nx[nu[a[i]][nu[a[i]].size()-k-1]]=nu[a[i]][nu[a[i]].size()-k];
}
}
create(1,1,n);
ll an=0;
for(int l=n;l;l--)
{
if(nx[l])
{
update(1,1,n,nxk[nx[l]],nxk1[nx[l]]-1,-1);
}
if(nxk[l])
{
update(1,1,n,nxk[l],nxk1[l]-1,1);
}
an+=answer(1,1,n,l,n);
}
cout<<an<<endl;
//system("pause");
return 0;
}