#include<bits/stdc++.h>
using namespace std;
#define sz(x) (int)x.size()

int read(){
	int a = 0; char c = getchar(); bool f = 0;
	while(!isdigit(c)){f = c == '-'; c = getchar();}
	while(isdigit(c)){
		a = a * 10 + c - 48; c = getchar();
	}
	return f ? -a : a;
}

#define ll long long
struct node{int plc , val , l , r;};
struct cmp1{bool operator ()(node a , node b){return a.plc < b.plc;}};
struct cmp2{bool operator ()(node a , node b){return a.val < b.val || a.val == b.val && a.plc < b.plc;}};
set < node , cmp1 > N1; set < node , cmp2 > N2;
int N , L; ll ans;

ll calc(vector < node > &cur){
	ll sum = 0 , all = 0;
	for(int i = 0 ; i + L - 1 < sz(cur) ; ++i){
		sum += cur[i].l;
		all += sum * cur[i + L - 1].r;
	}
	return all;
}

int main(){
	N = read(); L = read();
	for(int i = 1 ; i <= N ; ++i){
		node now; now.plc = i; now.val = read(); now.l = now.r = 1;
		N1.insert(now); N2.insert(now);
	}
	while(!N2.empty()){
		int val = N2.begin()->val; vector < node > mn;
		while(N2.begin()->val == val){mn.push_back(*N2.begin()); N2.erase(*N2.begin());}
		for(int i = 0 , pi = 1 ; i < sz(mn) ; i = pi , pi = i + 1){
			while(pi < sz(mn) && ++N1.find(mn[pi - 1]) == N1.find(mn[pi])) ++pi;
			vector < node > tmp; tmp.insert(tmp.end() , mn.begin() + i , mn.begin() + pi);
			int len = pi - i , cnt = len / L;
			if(cnt){
				ans += calc(tmp); vector < node > ntmp;
				for(auto t : tmp) N1.erase(t);
				for(int j = 0 ; j < cnt ; ++j) ntmp.push_back((node){tmp[0].plc + j , val + 1 , 0 , 0});
				for(int j = 0 ; j + L - 1 < sz(tmp) ; ++j) ntmp[cnt - (sz(tmp) - j) / L].l += tmp[j].l;
				for(int j = L - 1 ; j < sz(tmp) ; ++j) ntmp[(j + 1) / L - 1].r += tmp[j].r;
				ans -= calc(ntmp);
				for(auto t : ntmp){N1.insert(t); N2.insert(t);}
			}
		}
	}
	cout << ans + N;
	return 0;
}
