#include<stdio.h>
#include<queue>
std::priority_queue<std::pair<int,int>,std::vector<std::pair<int,int> >,std::greater<std::pair<int,int> > >Q;
int cntl[200002],cntr[200002],v[200002],tmp1[200002],tmp2[200002],tmp3[200002],r[200002],pool[200002],n,m;
long long ans;
long long calc(int n,int l[],int r[],int t[]){
	static std::queue<std::pair<int,int> >Q;
	while(!Q.empty())Q.pop();
	static int tmp1[200002],tmp2[200002];
	long long ans=0,cnt=0;int g=n/m;
	for(int i=1;i<=n;i++){
		Q.push(std::make_pair(t[i],l[i]));
		while(Q.size()>=m&&Q.front().first!=t[i])cnt+=Q.front().second,Q.pop();
		ans+=cnt*r[i];tmp1[i]=tmp2[i]=0;
	}for(int i=m;i<=n;i++)tmp2[i/m]+=r[i];
	for(int i=n-m+1;i>=1;i--)tmp1[g+1-(n+1-i)/m]+=l[i];
	for(int i=1;i<=g;i++)l[i]=tmp1[i],r[i]=tmp2[i];
	return ans;
}
int main(){
	scanf("%d%d",&n,&m);r[0]=1;ans=n;
	for(int i=1;i<=n;i++){
		int hdhdAKIOI;scanf("%d",&hdhdAKIOI);Q.push(std::make_pair(hdhdAKIOI,i));
		r[i]=i+1;v[i]=i;cntl[i]=cntr[i]=1;
	}while(!Q.empty()){
		int V=Q.top().first,tp=0;
		while(!Q.empty()&Q.top().first==V){
			pool[++tp]=Q.top().second;Q.pop();
		}tmp1[1]=cntl[pool[1]];tmp2[1]=cntr[pool[1]];tmp3[1]=v[pool[1]];
		for(int i=2,j=1;i<=tp;i++){
			if(r[pool[i-1]]==pool[i]){
				j++;tmp1[j]=cntl[pool[i]];tmp2[j]=cntr[pool[i]];tmp3[j]=v[pool[i]];
			}else{
				if(j>=m){
					ans+=calc(j,tmp1,tmp2,tmp3);
					int s=pool[i-j],c=j/m;
					for(int p=s;p<s+c-1;p++)r[p]=p+1;r[s+c-1]=r[pool[i-1]];
					for(int p=s;p<s+c;p++)cntl[p]=tmp1[p-s+1],cntr[p]=tmp2[p-s+1],v[p]=s,Q.push(std::make_pair(V+1,p));
				}j=1;tmp1[1]=cntl[pool[i]];tmp2[1]=cntr[pool[i]];tmp3[1]=v[pool[i]];
			}if(i==tp&&j>=m){
				ans+=calc(j,tmp1,tmp2,tmp3);
				int s=pool[i-j+1],c=j/m;
				for(int p=s;p<s+c-1;p++)r[p]=p+1;r[s+c-1]=r[pool[i]];
				for(int p=s;p<s+c;p++)cntl[p]=tmp1[p-s+1],cntr[p]=tmp2[p-s+1],v[p]=s,Q.push(std::make_pair(V+1,p));
			}
		}
	}printf("%lld",ans);
}