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<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#define ll long long
using namespace std;
int n,k,tot,pre[400005],nxt[400005],a[400005],l[400005],r[400005],sl[400005],sr[400005];
ll ans;
bool flag[400005];
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >q;
int main()
{
	scanf("%d%d",&n,&k);
	tot=n;
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		pre[i]=i-1,nxt[i]=i+1;
		q.push(make_pair(a[i],i));
		l[i]=r[i]=1;
	}
	nxt[n]=0;
	while(!q.empty())
	{
		int node=q.top().second;
		q.pop();
		if(flag[node])continue;
		int L=node,R=node,len=1;
		while(a[pre[L]]==a[node])L=pre[L],len++;
		while(a[nxt[R]]==a[node])R=nxt[R],len++;
		int last=0;
		for(int i=L,j=1;i!=nxt[R];i=nxt[i],j++)
		{
			sl[j]=sl[j-1]+l[i];
			sr[j]=sr[j-1]+r[i];
			if(i<=n)last=j;
			if(last&&j>=k)ans+=1ll*sl[min(j-k+1,last)]*r[i];
			flag[i]=1;
		}
		if(len<k)
		{
			nxt[pre[L]]=pre[nxt[R]]=0;
			continue;
		}
		for(int i=1;i<=len/k;i++)
		{
			r[tot+i]=sr[min(len,(i+1)*k-1)]-sr[i*k-1];
			l[tot+i]=sl[len-(len/k-i+1)*k+1]-sl[max(0,len-(len/k-i+2)*k+1)];
		}
		nxt[pre[L]]=tot+1,pre[tot+1]=pre[L];
		pre[nxt[R]]=tot+len/k,nxt[tot+len/k]=nxt[R];
		for(int i=1;i<len/k;i++)
		{
			nxt[tot+i]=tot+i+1;
			pre[tot+i+1]=tot+i;
		}
		for(int i=1;i<=len/k;i++)a[tot+i]=a[L]+1;
		q.push(make_pair(a[tot+1],tot+1));
		tot+=len/k;
	}
	printf("%lld\n",ans+n);
	return 0;
}