#include<bitset>
#include<cstdio>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
const int N=50009;
int n,m,p[N],id[N];
bitset<N> b[N],pre[N],suf[N],cur;
int bl[N],L[N],R[N];
bool cmp(const int &a,const int &b){
    return p[a]<p[b];
}
void solve(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%d",&p[i]),id[i]=i,bl[i]=(i-1)/m+1;
        if(!L[bl[i]]) L[bl[i]]=i;
        R[bl[i]]=i;
    }
    sort(id+1,id+1+n,cmp);
    for(int i=1;i<=n;i++){
        int u=id[i];
        b[u]=cur>>u+1;
        cur[u]=1;
    }
    // for(int i=1;i<=n;i++,puts(""))
    //     for(int d=0;d<n-i;d++) printf("%d ",(int)b[i][d]);
    for(int i=1;i<=bl[n];i++){
        pre[L[i]]=b[L[i]];
        for(int j=L[i]+1;j<=R[i];j++) pre[j]=pre[j-1]|b[j];
        suf[R[i]]=b[R[i]];
        for(int j=R[i]-1;j>=L[i];j--) suf[j]=suf[j+1]|b[j];
    }
    LL res=0;
    for(int i=1;i<=n-m;i++){
        //[i,i+m-1]
        //d<=n-m+1-i
        //0~n+m-i
        if(i==L[bl[i]]) res+=(n-m+1)-i-(suf[i].count()-(suf[i]>>n-m-i+1).count())/* ,printf("(%d,%d,%d)",(n-m+1)-i,suf[i].count(),(suf[i]>>n-m-i+1).count()) */;
        else cur=suf[i]|pre[i+m-1],res+=(n-m+1)-i-(cur.count()-(cur>>n-m-i+1).count())/* ,printf("(%d,%d,%d)",(n-m+1)-i,cur.count(),(cur>>n-m-i+1).count()) */;
        // printf("%lld ",res);
    }
    printf("%lld\n",res);
}
int main(){
    // freopen("t.in","r",stdin);
    // freopen("t.out","w",stdout);
    int T=1;
    // scanf("%d",&T);
    while(T--) solve();
    return 0;
}