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<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
int a[1000010];
struct Val{
	int pos,val;
	Val(int a=0,int b=0)
	{
		pos=a;
		val=b;
	}
};
bool operator <(const Val& a,const Val& b)
{
	return a.val>b.val;
}
priority_queue<Val>q;
int pre[2000010],nxt[2000010];
int f[2000010],g[2000010];
int sum1[2000010];
int sum2[2000010];
bool vis[2000010];
int main()
{
	long long ans=0;
	int n,L;
	scanf("%d %d",&n,&L);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		f[i]=g[i]=1;
		pre[i]=i-1;
		nxt[i]=i+1;
		q.push(Val(i,a[i]));
	}
	nxt[n]=0;
	int tot=n;
	while(!q.empty())
	{
		int pos=q.top().pos;
		q.pop();
		if(vis[pos])continue;
		int lpos=pos,rpos=pos;
		while(a[pre[lpos]]==a[pos])lpos=pre[lpos];
		while(a[nxt[rpos]]==a[pos])rpos=nxt[rpos];
		int cnt=0;
		int lst=0;
		for(int i=lpos;i!=nxt[rpos];i=nxt[i])
		{
			cnt++;
			if(i<=n)lst=cnt;
			sum1[cnt]=sum1[cnt-1]+f[i];
			sum2[cnt]=sum2[cnt-1]+g[i];
			vis[i]=true;
			if(lst&&cnt>=L)
				ans+=(long long)g[i]*sum1[min(lst,cnt-L+1)];
		}
		if(cnt<L){
			nxt[pre[lpos]]=pre[nxt[rpos]]=0;
			continue;
		}
		for(int i=1;i<cnt/L;i++)
		{
			nxt[tot+i]=tot+i+1;
			pre[tot+i+1]=tot+i;
		}
		for(int i=1;i<=cnt/L;i++)
			a[tot+i]=a[pos]+1;
		nxt[pre[lpos]]=tot+1;pre[tot+1]=pre[lpos];
		pre[nxt[rpos]]=tot+cnt/L;nxt[tot+cnt/L]=nxt[rpos];
		for(int i=1;i<=cnt/L;i++)
		{
			g[tot+i]=sum2[min((i+1)*L-1,cnt)]-sum2[i*L-1];
			int ii=cnt/L-i+1;
			f[tot+i]=sum1[cnt-ii*L+1]-sum1[max(cnt-(ii+1)*L+1,0)];
		}
		q.push(Val(tot+1,a[tot+1]));
		tot+=cnt/L;
		/*
		printf("current ans=%lld\n",ans);
		printf("a:");
		for(int i=nxt[0];i;i=nxt[i])
			printf(" %d",a[i]);
		printf("\nf:");
		for(int i=nxt[0];i;i=nxt[i])
			printf(" %d",f[i]);
		printf("\ng:");
		for(int i=nxt[0];i;i=nxt[i])
			printf(" %d",g[i]);
		printf("\n\n");
		*/
	}
	printf("%lld\n",ans+n);
	return 0;
}