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<set>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;
inline int read(){
	int x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-')f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		x=(x<<1)+(x<<3)+c-'0';
		c=getchar();
	}
	return x*f;
}
int n,L;
ll ans;
struct Inter{
	int pos,val,l,r;
	Inter(int _p=0,int _v=0,int _l=0,int _r=0){pos=_p,val=_v,l=_l,r=_r;}
};
struct cmp1{
	bool operator ()(const Inter a,const Inter b)const{
		return a.pos<b.pos;
	}
};
struct cmp2{
	bool operator ()(const Inter a,const Inter b)const{
		return a.val==b.val?a.pos<b.pos:a.val<b.val;
	}
};
set<Inter,cmp1> p;
set<Inter,cmp2> s;
inline ll calc(vector<Inter> &v){
	ll tot=0,sum=0;
	for(int i=0;i+L-1<(int)v.size();++i){
		sum+=v[i].l;
		tot+=sum*v[i+L-1].r;
	}
	return tot;
}
int main(){
	n=read(),L=read();
	for(int i=1;i<=n;++i){
		int x=read();
		Inter zyk(i,x,1,1);
		p.insert(zyk),s.insert(zyk);
	}
	while(!s.empty()){
		int w=s.begin()->val;
		vector<Inter> t;
		while(s.begin()->val==w){
			t.push_back(*s.begin());
			s.erase(s.begin());
		}
		for(int l=0,r=1;l<(int)t.size();l=r++){
			while(r<(int)t.size()&&(--p.find(t[r]))==p.find(t[r-1]))++r;
			int len=r-l,cnt=len/L;
			if(!cnt)continue;
			vector<Inter> myh,zyy;
			myh.insert(myh.begin(),t.begin()+l,t.begin()+r);
			for(auto x:myh){
				p.erase(x);
			}
			ans+=calc(myh);
			for(int i=0;i<cnt;++i){
				zyy.push_back(Inter(myh[0].pos+i,w+1,0,0));
			}
			for(int i=0;i+L-1<(int)myh.size();++i){
				zyy[cnt-((int)myh.size()-i)/L].l+=myh[i].l;
			}
			for(int i=L-1;i<(int)myh.size();++i){
				zyy[(i-L+1)/L].r+=myh[i].r;
			}
			ans-=calc(zyy);
			for(auto x:zyy){
				p.insert(x),s.insert(x);
			}
		}
	}
	printf("%lld\n",ans+n);
	return 0;
}

