For a sequence S of positive integers and positive integers k and l, S is said to belong to level (k,l) when one of the following conditions is satisfied:

* The length of S is 1, and its only element is k.
* There exist sequences T_1,T_2,...,T_m (m \geq l) belonging to level (k-1,l) such that the concatenation of T_1,T_2,...,T_m in this order coincides with S.



Note that the second condition has no effect when k=1, that is, a sequence belongs to level (1,l) only if the first condition is satisfied.

Given are a sequence of positive integers A_1,A_2,...,A_N and a positive integer L. Find the number of subsequences A_i,A_{i+1},...,A_j (1 \leq i \leq j \leq N) that satisfy the following condition:

* There exists a positive integer K such that the sequence A_i,A_{i+1},...,A_j belongs to level (K,L).

Constraints

* 1 \leq N \leq 2 \times 10^5
* 2 \leq L \leq N
* 1 \leq A_i \leq 10^9

Input

Input is given from Standard Input in the following format:


N L
A_1 A_2 ... A_N


Output

Print the number of subsequences A_i,A_{i+1},...,A_j (1 \leq i \leq j \leq N) that satisfy the condition.

Examples

Input

9 3
2 1 1 1 1 1 1 2 3


Output

22


Input

9 2
2 1 1 1 1 1 1 2 3


Output

41


Input

15 3
4 3 2 1 1 1 2 3 2 2 1 1 1 2 2


Output

31
#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

typedef long long ll;
const int Maxn = 2e5;

int N, L;
int A[Maxn + 5];

int tot;
int val[Maxn * 4 + 5], vl[Maxn * 4 + 5], vr[Maxn * 4 + 5];
int s1[Maxn * 4 + 5], s2[Maxn * 4 + 5], sum[Maxn * 4 + 5];
int now[Maxn * 4 + 5], newnow[Maxn * 4 + 5];

struct cmp {
	bool operator () (const int &lhs, const int &rhs) {
		return val[lhs] == val[rhs] ? vl[lhs] > vl[rhs] : val[lhs] > val[rhs];
	}
};
priority_queue<int, vector<int>, cmp> q;

int main() {
#ifdef LOACL
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
#endif
	scanf("%d %d", &N, &L);
	for(int i = 1; i <= N; i++) {
		scanf("%d", &A[i]);
		++tot;
		val[tot] = A[i], vl[tot] = vr[tot] = i;
		s1[tot] = s2[tot] = 1;
		q.push(tot);
	}
	ll ans = 0;
	while(!q.empty()) {
		int len = 0;
		now[++len] = q.top();
		q.pop();
		while(!q.empty() && val[q.top()] == val[now[1]] && vl[q.top()] == vr[now[len]] + 1)
			now[++len] = q.top(), q.pop();
		sum[0] = 0;
		for(int i = 1; i <= len; i++)
			sum[i] = sum[i - 1] + s1[now[i]];
		for(int i = 1; i <= len; i++) {
			ans += 1LL * s1[now[i]] * s2[now[i]];
			if(i - L + 1 >= 1) ans += 1LL * s2[now[i]] * sum[i - L + 1];
		}
		int newlen = 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++)
				s2[tot] += s2[now[j]];
			s1[tot] = sum[len % L + 1 + (i - 1) * L] - sum[last];
			last = len % L + 1 + (i - 1) * L;
			q.push(tot);
			newnow[++newlen] = tot;
		}
		sum[0] = 0;
		for(int i = 1; i <= newlen; i++)
			sum[i] = sum[i - 1] + s1[newnow[i]];
		for(int i = 1; i <= newlen; i++) {
			ans -= 1LL * s1[newnow[i]] * s2[newnow[i]];
			if(i - L + 1 >= 1) ans -= 1LL * s2[newnow[i]] * sum[i - L + 1];
		}
	}
	printf("%lld\n", ans);
	return 0;
}