#include <set>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define N 400005
#define ll long long
int n, l, tot;
int A[N], now[N], nnow[N], pre[N];
int val[N], vl[N], vr[N], suml[N], sumr[N];
ll ans;
struct cmp
{
	bool operator ()(const int &a,const int &b)
	{
		if (val[a] != val[b])
			return val[a] < val[b];
		return vl[a] < vl[b];
	}
};
set<int, cmp>s;
int main()
{
	scanf("%d%d", &n, &l);
	for (int i = 1; i <= n; i++)
	{
		scanf("%d", &A[i]);
		++tot;
		vl[tot] = vr[tot] = i;
		val[tot] = A[i];
		suml[tot] = sumr[tot] = 1;
		s.insert(tot);
	}
	while (!s.empty())
	{
		int len = 0;
		now[++len] = *s.begin();
		s.erase(s.begin());
		while (!s.empty() && val[*s.begin()] == val[now[1]] && vl[*s.begin()] == vr[now[len]] + 1)
		{
			now[++len] = *s.begin();
			s.erase(s.begin());
		}
		pre[0] = 0;
		for (int i = 1; i <= len; i++)
			pre[i] = pre[i - 1] + suml[now[i]];
		for (int i = 1; i <= len; i++)
		{
			ans += (ll)suml[now[i]] * sumr[now[i]]; 
			if (i - l + 1 >= 1)
				ans += (ll)sumr[now[i]] * pre[i - l + 1];
		}
		int nlen = 0, last = 0;
		for (int i = 1; i <= len / l; i++)
		{
			int tmpl = (i - 1) * l + 1, tmpr = i * l;
			if (i == len / l)
				tmpr = len;
			tot++;
			vl[tot] = vl[now[tmpl]];
			vr[tot] = vr[now[tmpr]];
			val[tot] = val[now[1]] + 1;
			for (int j = i * l; j <= (i + 1) * l - 1 && j <= len; j++)
				sumr[tot] += sumr[now[j]];
			suml[tot] = pre[len % l + 1 + (i - 1) * l] - pre[last];
			last = len % l + 1 + (i - 1) * l;
			s.insert(tot);
			nnow[++nlen] = tot;
		}
		pre[0] = 0;
		for (int i = 1; i <= nlen; i++)
			pre[i] = pre[i - 1] + suml[nnow[i]];
		for (int i = 1; i <= nlen; i++)
		{
			ans -= (ll)suml[nnow[i]]*sumr[nnow[i]];
			if (i - l + 1 >= 1)
				ans -= (ll)sumr[nnow[i]] * pre[i - l + 1];
		}
	}
	printf("%lld\n", ans);
}
