#include<bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define uint unsigned
#define pii pair<int,int>
#define pll pair<ll,ll>
#define PB push_back
#define fi first
#define se second
#define For(i,j,k) for (int i=(int)(j);i<=(int)(k);i++)
#define Rep(i,j,k) for (int i=(int)(j);i>=(int)(k);i--)
#define CLR(a,v) memset(a,v,sizeof(a));
#define CPY(a,b) memcpy(a,b,sizeof(a));
using namespace std;
const int N=200005;
priority_queue<pii,vector<pii>,greater<pii> > Q;
int pre[N],suf[N],q[N];
int a[N],l[N],r[N],n,L;
int Sl[N],Sr[N];
ll ans;
void erase(int x){
	suf[pre[x]]=suf[x];
	pre[suf[x]]=pre[x];
}
void work(){
	//printf("work %d %d\n",*q,ans);
	//For(i,1,*q) printf("%d %d %d\n",q[i],l[i],r[i]); puts("");
	int m=*q,pl,pr;
	q[0]=pre[q[1]];
	q[m+1]=suf[q[m]];
	Sl[0]=Sr[m+1]=0;
	For(i,1,m+1) Sl[i]=Sl[i-1]+l[q[i]];
	Rep(i,m,0) Sr[i]=Sr[i+1]+r[q[i]];
	For(i,L,m) ans+=1ll*r[q[i]]*Sl[i-L+1];
	pl=m+1,pr=max(1,m-L+2);
	Rep(i,m/L,1){
		pl-=L; pr=max(1,pr-L);
		l[q[i]]=Sl[pl]-Sl[pr-1];
	}
	pl=0,pr=min(m,L-1);
	For(i,1,m/L){
		pl+=L; pr=min(m,pr+L);
		r[q[i]]=Sr[pl]-Sr[pr+1];
	}
	if (m<L){
		For(i,2,m) erase(q[i]);
		a[q[1]]=1<<30;
		Q.push(pii(a[q[1]],q[1]));
	}
	else{
		For(i,1,m/L) ++a[q[i]];
		For(i,1,m/L) Q.push(pii(a[q[i]],q[i]));
		For(i,m/L+1,m) erase(q[i]);
		For(i,1,m/L) Sl[i]=Sl[i-1]+l[q[i]];
		For(i,L,m/L) ans-=1ll*r[q[i]]*Sl[i-L+1];
	}
}
int main(){
	scanf("%d%d",&n,&L);
	For(i,1,n) scanf("%d",&a[i]);
	For(i,1,n) l[i]=r[i]=1;
	For(i,1,n) pre[i]=i-1,suf[i]=i+1;
	For(i,1,n) Q.push(pii(a[i],i));
	while (!Q.empty()){
		q[++*q]=Q.top().se; Q.pop();
		if (a[q[1]]==1<<30) break;
		for (;!Q.empty()&&Q.top().fi==a[q[*q]];){
			int tmp=Q.top().se; Q.pop();
			if (tmp!=suf[q[*q]]) work(),*q=0;
			q[++*q]=tmp;
		}
		work(); *q=0;
	}
	printf("%lld\n",ans+n);
}