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<bits/stdc++.h>
using namespace std;

bool bo[400010];
int n,L,sum[400010],a[400010],tot,q[400010],l,r,fl[400010],fr[400010],pre[400010],suf[400010],t[400010],tn,Q[400010],Qn,x,nxt[400010];
pair<int,int> val[200010];
long long ans;

int main()
{
	scanf("%d%d",&n,&L),a[0]=a[n+1]=-1;
	for (int i=1; i<=n; i++) scanf("%d",&a[i]),val[i]=make_pair(a[i],i),fl[i]=fr[i]=1;
	sort(val+1,val+1+n),l=200000,r=l-1,suf[0]=1,pre[n+1]=n,tot=n+1,ans=n;
	for (int i=1; i<=n; i++) q[++r]=val[i].second,pre[i]=i-1,suf[i]=i+1;
	while (l<=r)
	{
		int R=l;
		while (R<r&&a[q[R+1]]==a[q[l]]) R++;
		for (int i=l; i<=R; i++) if (!bo[q[i]])
		{
			x=q[i];
			while (a[pre[x]]==a[x]) x=pre[x];
			t[tn=1]=x,bo[x]=1;
			while (a[suf[x]]==a[x]) x=suf[x],t[++tn]=x,bo[x]=1;
			nxt[tn+1]=tn+1;
			for (int j=tn; j; j--) if (t[j]<=n) nxt[j]=j; else nxt[j]=nxt[j+1];
			sum[tn+1]=0;
			for (int j=tn; j; j--) sum[j]=sum[j+1]+fr[t[j]];
			for (int j=1; j<=tn; j++) ans+=1ll*fl[t[j]]*sum[min(max(j+L-1,nxt[j]),tn+1)];
			if (tn>=L) for (int j=1; j<=tn; j++) pre[suf[t[j]]]=pre[t[j]],suf[pre[t[j]]]=suf[t[j]];
			int pr=pre[t[1]],sf=suf[t[tn]],cnt=tn/L;
			for (int j=1; j<=cnt; j++) suf[pr]=(++tot),a[tot]=a[t[1]]+1,pre[sf]=tot,pre[tot]=pr,suf[tot]=sf,pr=tot,Q[++Qn]=tot;
			for (int j=1; j<=cnt; j++)
			{
				fr[tot-cnt+j]=0;
				for (int k=j*L; k<(j+1)*L&&k<=tn; k++) fr[tot-cnt+j]+=fr[t[k]];
			}
			for (int j=cnt; j; j--)
			{
				fl[tot-cnt+j]=0;
				for (int k=tn-(cnt-j+1)*L+1; k>tn-(cnt-j+2)*L+1&&k; k--) fl[tot-cnt+j]+=fl[t[k]];
			}
		}
		l=R+1;
		for (int i=1; i<=Qn; i++) q[--l]=Q[i];
		Qn=0;
	}
	return printf("%lld\n",ans),0;
}