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 <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);
}
