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;

#define rep(i,n) for(int i=0;i<(n);i++)
#define REP(i,n) for(int i=1;i<=(n);i++)
#define mp make_pair
#define pb push_back
#define fst first
#define snd second
typedef long long ll;
typedef pair<int,int> pii;

const int maxn=200005;
int n,l,tot;
int a[maxn],now[maxn*2],nnow[maxn*2],pre[maxn*2];
int val[maxn*2],vl[maxn*2],vr[maxn*2],suml[maxn*2],sumr[maxn*2];
ll ans;
class Cmp{
public:
	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);
	REP(i,n){
		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;
		REP(i,len)pre[i]=pre[i-1]+suml[now[i]];
		REP(i,len){
			ans+=1LL*suml[now[i]]*sumr[now[i]];
			if(i-l+1>=1)ans+=1LL*sumr[now[i]]*pre[i-l+1];
		}
		int nlen=0,last=0;
		REP(i,len/l){
			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;
		REP(i,nlen)pre[i]=pre[i-1]+suml[nnow[i]];
		REP(i,nlen){
			ans-=1LL*suml[nnow[i]]*sumr[nnow[i]];
			if(i-l+1>=1)ans-=1LL*sumr[nnow[i]]*pre[i-l+1];
		}
	}
	printf("%lld\n",ans);
	return 0;
}