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<cstring>
#include<vector>
#include<algorithm>
#include<set>
#include<cmath>
#include<cstdlib>
#define LL long long
#define LD long double
using namespace std;
const int NN=200000 +117;
const int MM=200000 +117;
int read(){
	int fl=1,x;char c;
	for(c=getchar();(c<'0'||c>'9')&&c!='-';c=getchar());
	if(c=='-'){fl=-1;c=getchar();}
	for(x=0;c>='0'&&c<='9';c=getchar())
		x=(x<<3)+(x<<1)+c-'0';
	return x*fl;
}
void open(){
	freopen("a.in","r",stdin);
	//freopen("a.out","w",stdout);
}
void close(){
	fclose(stdin);
	fclose(stdout);
}

#define pii pair<int,int>
#define mp make_pair 
int m,n,l;
int a[NN]={};
int v[NN][2]={};
int xt[NN]={};
int pre[NN]={};
set<pii> all;
int tp[NN][2]={};
int sum[NN]={};
int id[NN]={};
int res[NN][2]={};
LL calc(int v[NN][2],int len){
	for(int i=1;i<=len;++i){
		sum[i]=sum[i-1]+v[i][1];
	}
	LL ans=0;
	for(int i=1;i+l-1<=len;++i){
		ans+=(LL)v[i][0]*(sum[len]-sum[i+l-2]);
	}
	return ans;
}
int main(){
	//open();
	n=read();
	l=read();
	LL ans=n;
	for(int i=1;i<=n;++i){
		a[i]=read();
		all.insert(mp(a[i],i));
		v[i][0]=v[i][1]=1;
		xt[i]=i+1;
		pre[i]=i-1;
	}
	while(!all.empty()){
		pii now=*all.begin();
		int val=now.first;
		int pos=now.second;
		int cnt=0;
		while(a[pos]==val){
			tp[++cnt][0]=v[pos][0];
			tp[cnt][1]=v[pos][1];
			id[cnt]=pos;
			all.erase(mp(val,pos));
			pos=xt[pos];
		}
		if(cnt>=l){
			ans+=calc(tp,cnt);
			int bcnt=cnt/l;
			for(int i=1;i<=bcnt;++i){
				res[i][0]=res[i][1]=0;
			}
			for(int i=l;i<=cnt;++i){
				res[i/l][1]+=tp[i][1];
			}
			for(int i=cnt-l+1;i>=1;--i){
				res[bcnt+1-(cnt+1-i)/l][0]+=tp[i][0];
			}
			ans-=calc(res,bcnt);
			for(int i=1;i<=bcnt;++i){
				int pos=id[i];
				all.insert(mp(val+1,pos));
				a[pos]=val+1;
				v[pos][0]=res[i][0];
				v[pos][1]=res[i][1];
			}
			xt[id[bcnt]]=xt[id[cnt]];
			pre[xt[id[bcnt]]]=id[bcnt];
		}
	}
	printf("%lld\n",ans);
	close();
	return 0;
}