#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e6+10;
struct node
{
  int l,r,minnum,min1;
  int lazy;
}tr[N<<2];
vector<int> pos[N];
pair<int,int> p[N];
pair<int,int> p1[N];
int cnt[N];
void pushup(int u)
{
  if(tr[u<<1].min1<tr[u<<1|1].min1)
  {
    tr[u].min1=tr[u<<1].min1;
    tr[u].minnum=tr[u<<1].minnum;
  }
  else if(tr[u<<1].min1<tr[u<<1|1].min1)
  {
     tr[u].min1=tr[u<<1|1].min1;
    tr[u].minnum=tr[u<<1|1].minnum;
  }
  else
  {
     tr[u].min1=tr[u<<1].min1;
    tr[u].minnum=tr[u<<1].minnum+tr[u<<1|1].minnum;
  }
}
void pushdown(int u)
{
  tr[u<<1].min1+=tr[u].lazy;
  tr[u<<1|1].min1+=tr[u].lazy;
  tr[u<<1].lazy+=tr[u].lazy;
  tr[u<<1|1].lazy+=tr[u].lazy;
  tr[u].lazy=0;
}
void build(int u,int l,int r)
{
  tr[u].l=l;
  tr[u].r=r;
  if(l==r)
  {
    tr[u].min1=0;
    tr[u].minnum=1;
  }
  else
  {
    int mid=l+r>>1;
    build(u<<1,l,mid);
    build(u<<1|1,mid+1,r);
    pushup(u);
  }
}
void modify(int u,int l,int r,int x)
{
  if(l<=tr[u].l&&tr[u].r<=r)
  {
    tr[u].min1+=x;
    tr[u].lazy+=x;
  }
  else
  {
    pushdown(u);
    int mid=tr[u].l+tr[u].r>>1;
    if(l<=mid) modify(u<<1,l,r,x);
    if(r>mid) modify(u<<1|1,l,r,x);
    pushup(u);
  }
}
int query(int u,int l,int r)
{
  if(l<=tr[u].l&&tr[u].r<=r)
  {
    if(tr[u].min1==0) return tr[u].minnum;
    else return 0;
  }
  else
  {
    pushdown(u);
    int mid=tr[u].l+tr[u].r>>1;
    int ans=0;
    if(l<=mid) ans+=query(u<<1,l,r);
    if(r>mid) ans+=query(u<<1|1,l,r);
    return ans;
  }
}
signed main()
{
  int n,k;
  cin>>n>>k;
  vector<int> a(n+1,0);
  for(int i=1;i<=n;i++)
  {
    cin>>a[i];
    pos[a[i]].push_back(i);
  }
  int ans=0;
  memset(p,-1,sizeof p);
  //memset(p1,-1,sizeof p1);
  build(1,1,n);
  for(int i=1;i<=n;i++)
  {
    int t=a[i];
    if(pos[a[i]][0]!=i) continue;
    if(pos[a[i]].size()<k) continue;
    int l=pos[a[i]][k-1];
    int r;
    if(pos[a[i]].size()==k) r=n;
    else r=pos[a[i]][k]-1;
    p[a[i]]={l,r};
    modify(1,l,r,1);
  }
  for(int i=1;i<=n;i++)
  {
    int pre=a[i-1];
    if(p[pre].first!=-1)
    {
      modify(1,p[pre].first,p[pre].second,-1);
      int sz=pos[pre].size();
      if(sz-1>=cnt[pre]+k-1)
      {
        int l=pos[pre][cnt[pre]+k-1];
        int r;
        if(pos[pre].size()<=k+cnt[pre]) r=n;
        else r=pos[pre][cnt[pre]+k]-1;
        modify(1,l,r,1);
        p[pre].first=l;
        p[pre].second=r;
      }
      else
      {
        p[pre].first=-1;
        p[pre].second=-1;
      }
    }
    int len=query(1,i,n);
    ans+=len;
   // cout<<len<<"aa"<<endl;
    cnt[a[i]]++; 
  }
  cout<<ans<<endl;




}