#include<bits/stdc++.h>
using namespace std;
const int MAX=1e6+6;
int n,k;
int mins[MAX*4],tag[MAX*4],a[MAX],d[MAX][2],nxt[MAX],cnt[MAX*4];
vector<int> g[MAX];
long long ans;
void add(int k,int l,int r,int v){
    tag[k]+=v;
    mins[k]+=v;
}
void pushdown(int k,int l,int r){
    if(!tag[k])
        return;
    int mid=l+r>>1;
    add(k<<1,l,mid,tag[k]);
    add(k<<1|1,mid+1,r,tag[k]);
    tag[k]=0;
}
void modify(int k,int l,int r,int x,int y,int v){
    if(l>=x&&r<=y){
        return add(k,l,r,v);
    }

    pushdown(k,l,r);

    int mid=l+r>>1;
    if(x<=mid){
        modify(k<<1,l,mid,x,y,v);
    }
    if(mid<y){
        modify(k<<1|1,mid+1,r,x,y,v);
    }

    mins[k]=min(mins[k<<1],mins[k<<1|1]);
    cnt[k]=0;
    if(mins[k<<1]==mins[k])
        cnt[k]+=cnt[k<<1];
    if(mins[k<<1|1]==mins[k])
        cnt[k]+=cnt[k<<1|1];
}
void build(int k,int l,int r){
    if(l==r){
        cnt[k]=1;
        return;
    }
    int mid=l+r>>1;
    build(k<<1,l,mid);
    build(k<<1|1,mid+1,r);
    cnt[k]=cnt[k<<1]+cnt[k<<1|1];
}
int main(){
//    freopen("in.txt","r",stdin);
//    freopen("out.txt","w",stdout);
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

    cin>>n>>k;
    for(int i=1;i<=n;++i){
        cin>>a[i];
        g[a[i]].push_back(i);
    }

    build(1,1,n);
    for(int i=1;i<=(int)1e6;++i){
        for(int j=0;j<(int)g[i].size()-k+1;++j){
            d[g[i][j]][0]=g[i][j+k-1];
            if(j!=(int)g[i].size()-1-k+1){
                nxt[g[i][j]]=g[i][j+1];
                d[g[i][j]][1]=g[i][j+k];
            }
            else{
                d[g[i][j]][1]=n;
            }
            if(j==0){
                modify(1,1,n,d[g[i][j]][0],d[g[i][j]][1],1);
            }
        }
    }

    for(int i=1;i<=n;++i){
        if(mins[1]==0){
            ans+=n-cnt[1];
        }
        else{
            ans+=n;
        }
        if(d[i][0]){
            modify(1,1,n,d[i][0],d[i][1],-1);
        }
        if(nxt[i]){
            modify(1,1,n,d[nxt[i]][0],d[nxt[i]][1],1);
        }
    }

    cout<<1LL*n*(n+1)/2-ans;
}