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<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long ll;
const int N=200005;
int n,l,p,v,a[N];
ll ans;
vector<pair<int,int> > b,t1,t2,t3;
vector<pair<pair<int,int>,pair<int,int> > > x,y;
ll calc(vector<pair<int,int> > &x){
	ll sum=0,res=0;
	for(unsigned i=l-1,j=0;i<x.size();i++,j++){
		sum+=x[j].first;
		res+=x[i].second*sum;
	}
	return res;
}
int main(){
	scanf("%d%d",&n,&l);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		b.push_back(make_pair(a[i],i));
	}
	sort(b.begin(),b.end());
	while(1){
		if(x.empty()){
			if(p==n){
				break;
			}else{
				v=b[p].first;
			}
		}else{
			v++;
		}
		while(p<n&&b[p].first==v){
			x.push_back(make_pair(make_pair(b[p].second,b[p].second),make_pair(1,1)));
			p++;
		}
		y.clear();
		sort(x.begin(),x.end());
		for(unsigned i=0,j;i<x.size();i=j+1){
			j=i;
			while(j+1<x.size()&&x[j+1].first.first==x[j].first.second+1){
				j++;
			}
			int len=j-i+1,tot=len/l;
			if(tot){
				t1.clear();
				for(unsigned k=i;k<=j;k++){
					t1.push_back(x[k].second);
				}
				ans+=calc(t1);
				t2.clear();
				t3.clear();
				for(int k=1;k<=tot;k++){
					t2.push_back(make_pair(x[i].first.first+k-1,k==tot?x[j].first.second:x[i].first.first+k-1));
					t3.push_back(make_pair(0,0));
				}
				for(unsigned k=i;k<=j;k++){
					int l1=k-i+1,l2=j-k+1;
					if(l1>=l){
						t3[l1/l-1].second+=x[k].second.second;
					}
					if(l2>=l){
						t3[tot-l2/l].first+=x[k].second.first;
					}
				}
				ans-=calc(t3);
				for(int k=0;k<tot;k++){
					y.push_back(make_pair(t2[k],t3[k]));
				}
			}
		}
		x=y;
	}
	printf("%lld\n",ans+n);
	return 0;
}