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>
#define ld double
#define ull unsigned long long
#define ll long long
#define pii pair<int,int >
#define iiii pair<pii,pii >
#define mp make_pair
#define INF 1000000000
#define MOD 1000000007
#define rep(i,x) for(int (i)=0;(i)<(x);(i)++)
inline int getint(){
	int x=0,p=1;char c=getchar();
	while (c<=32)c=getchar();
	if(c==45)p=-p,c=getchar();
	while (c>32)x=x*10+c-48,c=getchar();
	return x*p;
}
using namespace std;
//ruogu_alter
const int N=2e5+5;
int n,l;
ll res;
pii b[N];
vector<iiii >a;
//
inline ll calc(vector<pii >&v){
	ll ans=0,sum=0;
	for(int i=l-1,j=0;i<v.size();i++,j++){
		sum+=1ll*v[j].first;
		ans+=1ll*v[i].second*sum;
	}
	return ans;
}
int main(){
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	n=getint();l=getint();
	rep(i,n){
		int x=getint();
		b[i]=mp(x,i);
	}
	sort(b,b+n);
	int pos=0,val=0;res=1ll*n;
	while(1){
		if(a.empty()){
			if(pos==n)break;
			else val=b[pos].first;
		}
		else ++val;
		while(pos<n&&b[pos].first==val){
			a.emplace_back(pii(b[pos].second,b[pos].second),pii(1,1));
			++pos;
		}
		sort(a.begin(),a.end());
		vector<iiii >toa;
		for(int i=0,j;i<a.size();i=j+1){
			j=i;while(j<a.size()-1&&a[j].first.second+1==a[j+1].first.first)++j;
			int len=j-i+1,cnt=len/l;
			if(cnt){
				vector<pii >v,posx,posy;
				for(int k=i;k<=j;k++)v.push_back(a[k].second);
				res+=calc(v);
				rep(k,cnt){
					posx.emplace_back(a[i].first.first+k,a[i].first.first+k);
					posy.emplace_back(0,0);
					if(k==cnt-1)posx.back().second=a[j].first.second;
				}
				for(int k=i;k<=j;k++){
					int tx=k-i+1,ty=j-k+1;
					if(tx>=l)posy[tx/l-1].second+=a[k].second.second;
					if(ty>=l)posy[cnt-ty/l].first+=a[k].second.first;
				}
				res-=calc(posy);
				rep(k,posx.size())toa.emplace_back(posx[k],posy[k]);
			}
		}
		a=toa;
	}
	printf("%lld\n",res);
	return 0;
}
