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 ll long long
using namespace std;
template<typename tn> void read(tn &a){
	tn x=0,f=1; char c=' ';
	for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
	for(;isdigit(c);c=getchar()) x=x*10+c-'0';
	a=x*f;
}
typedef pair<int,int> pr;
ll ans;
int n,L;
pr p[201000];
ll calc(vector<pair<pr,pr> > v){
	ll now=0;
//	for(auto&x:v) now+=x.second.first*x.second.second;
	ll s=0;
	for(int i=0,j=L-1;j<v.size();i++,j++)
		s+=v[i].second.first,now+=v[j].second.second*s;
	return now;
}
vector<pair<pr,pr> > merge(vector<pair<pr,pr> > v){
	vector<pair<pr,pr> > res;
	if(v.size()<L) return res;
	int cnt=v.size()/L;
	for(int i=0;i<cnt;i++)
		res.emplace_back(pr{v[i*L].first.first,i==cnt-1?v.back().first.second:v[i*L+L-1].first.second},pr{0,0});
	for(int i=0;i<v.size();i++){
		if(i+1>=L) res[(i+1)/L-1].second.second+=v[i].second.second;
		if(v.size()-i>=L) res[cnt-(v.size()-i)/L].second.first+=v[i].second.first;
	}
	ans-=calc(res);
	return res;
}
int main(){
	read(n);read(L);
	for(int i=1;i<=n;i++){
		int x;read(x);
		p[i]=pr{x,i};
	}
	sort(p+1,p+n+1);
	int now=1,k;ans=n;
	vector<pair<pr,pr> > v;
	while(!v.empty()||now<=n){
		if(v.empty()) k=p[now].first;
		else k++;
		while(now<=n&&k==p[now].first) v.emplace_back(pr{p[now].second,p[now].second},pr{1,1}),now++;
		sort(v.begin(),v.end());
		vector<pair<pr,pr> > nxt;
		for(int i=0,j=0;i<v.size();i=++j){
			vector<pair<pr,pr> > res;
			res.push_back(v[i]);
			while(j+1<v.size()&&v[j+1].first.first==v[j].first.second+1) res.push_back(v[++j]);
			ans+=calc(res);
			for(auto&x:merge(res)) nxt.push_back(x);
		}
		v=nxt;
	}
	cout<<ans<<'\n';
	return 0;
}
