#include<bits/stdc++.h>
#define ll long long 
#define N 1000005
using namespace std;
int n,k,a[N];
vector<int> v[N];
struct node{
    int l,r,v;
};
vector<node> q[N];
int mn[N<<3],cnt[N<<3],tg[N<<3];
void build(int x,int l,int r){
    if(l==r){
        mn[x]=0,cnt[x]=1;
        return;
    }
    int mid=l+r>>1;
    build(x<<1,l,mid);
    build(x<<1|1,mid+1,r);
    mn[x]=0;
    cnt[x]=cnt[x<<1]+cnt[x<<1|1];
}
void pushdown(int x){
    if(tg[x]){
        mn[x<<1]+=tg[x],tg[x<<1]+=tg[x];
        mn[x<<1|1]+=tg[x],tg[x<<1|1]+=tg[x];
        tg[x]=0;
    }
}
void modify(int x,int l,int r,int L,int R,int v){
    if(L<=l&&r<=R){
        mn[x]+=v;
        tg[x]+=v;
        return;
    }
    pushdown(x);
    int mid=l+r>>1;
    if(L<=mid) modify(x<<1,l,mid,L,R,v);
    if(R>mid) modify(x<<1|1,mid+1,r,L,R,v);
    mn[x]=min(mn[x<<1],mn[x<<1|1]);
    cnt[x]=0;
    if(mn[x<<1]==mn[x]) cnt[x]+=cnt[x<<1];
    if(mn[x<<1|1]==mn[x]) cnt[x]+=cnt[x<<1|1];
}
int qry(int x,int l,int r,int L,int R){
    if(L<=l&&r<=R){
        if(mn[x]==0) return cnt[x];
        return 0; 
    }
    int mid=l+r>>1,res=0;
    if(L<=mid) res+=qry(x<<1,l,mid,L,R);
    if(R>mid) res+=qry(x<<1|1,mid+1,r,L,R);
    return res;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>k;
    for(int i=1;i<=n;++i){
        cin>>a[i];
        if(v[a[i]].size()==0) v[a[i]].push_back(0);
        v[a[i]].push_back(i);
    }
    for(int i=1;i<=1000000;++i){
        if(v[i].size()>=k+1){
            v[i].push_back(n+1);
            int sz=v[i].size();
            for(int j=1;j+k<sz;++j){
                q[v[i][j-1]+1].push_back((node){v[i][j+k-1],v[i][j+k]-1,1});
                q[v[i][j]+1].push_back((node){v[i][j+k-1],v[i][j+k]-1,-1});
            }
        }
    }
    build(1,1,n);
    ll ans=0;
    for(int i=1;i<=n;++i){
        for(auto v:q[i])
            modify(1,1,n,v.l,v.r,v.v);
        ans+=qry(1,1,n,i,n);
    }
    cout<<ans<<'\n';
    return 0;
}