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<cstdio>
#include<queue>
using namespace std;
#define N 200127
#define INF 0x3f3f3f3f
int n,m,a[N],mi=INF,L[N],R[N],vl[N],vr[N],v1[N],v2[N];
struct Point{
	int x,v;
	inline bool operator<(const Point &b)const{return (v>b.v)||((v==b.v)&&(x>b.x));}
};
priority_queue<Point>q;
int b[N],cn=0;long long ans=0;
int main(){
	scanf("%d%d",&n,&m);ans=n;int i,j,k,v,l,r,p,sum;for(i=1;i<=n;i++)scanf("%d",&a[i]),L[i]=i-1,R[i]=i+1,vl[i]=vr[i]=1,q.push((Point){i,a[i]});
	while(!q.empty())
	{
		cn=0;v=q.top().v;while((!q.empty())&&(v==q.top().v))b[++cn]=q.top().x,q.pop();
		for(i=1;i<=cn;i=r+1)
		{
			l=r=i;while((r<cn)&&(R[b[r]]==b[r+1]))++r;
			sum=0;for(i=l;i<=r;i++){if(i-m+1>=l)sum+=vl[b[i-m+1]];ans+=1ll*sum*vr[b[i]];}
			if(r-l+1<m){R[L[b[l]]]=n+1;L[R[b[r]]]=0;continue;}p=(r-l+1)/m;
			for(i=l;i<=r;i++)k=b[i],v1[k]=vl[k],v2[k]=vr[k],vl[k]=vr[k]=0;
			for(i=r-m+1,k=p;i>=l;i-=m,--k)for(j=i;(j>=l)&&(j>=i-m+1);j--)vl[b[l+k-1]]+=v1[b[j]];
			for(i=l+m-1,k=1;i<=r;i+=m,++k)for(j=i;(j<=r)&&(j<=i+m-1);j++)vr[b[l+k-1]]+=v2[b[j]];
			for(i=l;i<=l+p-1;i++)++a[b[i]],q.push((Point){b[i],a[b[i]]});L[R[b[r]]]=b[l+p-1];R[b[l+p-1]]=R[b[r]];
			sum=0;for(i=l;i<=l+p-1;i++){if(i-m+1>=l)sum+=vl[b[i-m+1]];ans-=1ll*sum*vr[b[i]];}
		}
	}printf("%lld",ans);return 0;
}