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 fi first
#define se second
#define pb push_back
#define SZ(x) ((int)x.size())
#define L(i,u) for (register int i=head[u]; i; i=nxt[i])
#define rep(i,a,b) for (register int i=(a); i<=(b); i++)
#define per(i,a,b) for (register int i=(a); i>=(b); i--)
using namespace std;
typedef long long ll;
typedef unsigned int ui;
typedef pair<int,int> Pii;
typedef vector<Pii> Vp;
template<class T> inline void read(T &x){
	x=0; char c=getchar(); int f=1;
	while (!isdigit(c)) {if (c=='-') f=-1; c=getchar();}
	while (isdigit(c)) {x=x*10+c-'0'; c=getchar();} x*=f;
}
template<class T> inline void umin(T &x, T y){x=x<y?x:y;}
template<class T> inline void umax(T &x, T y){x=x>y?x:y;}
inline ui R() {
	static ui seed=416;
	return seed^=seed>>5,seed^=seed<<17,seed^=seed>>13;
}
const int N = 266666, inf = 0x3f3f3f3f;
int n,l,a[N];ll res;map<Pii,Vp>Set;//pos,val: vector<Pii>
set<Pii>heap;//val,pos
void merge_front(map<Pii,Vp>::iterator it){
	if(it==Set.begin())return;map<Pii,Vp>::iterator it1=it;it1--;
	if((*it).fi.se!=(*it1).fi.se)return;
//	cerr<<"merge "<<(*it).fi.fi<<' '<<(*it1).fi.fi<<endl;
	heap.erase(Pii((*it).fi.se,(*it).fi.fi));
	rep(i,0,SZ((*it).se)-1)(*it1).se.pb((*it).se[i]);Set.erase(it);
}
inline ll calc(Vp a){
	static ll qz[N];
	rep(i,0,SZ(a)-1)qz[i]=(i-1>=0?qz[i-1]:0)+a[i].fi;
	ll res=0;rep(i,l-1,SZ(a)-1)res+=qz[i-l+1]*a[i].se;
	rep(i,0,SZ(a)-1)res+=1LL*a[i].fi*a[i].se;
	return res;
}
int main() {
	read(n);read(l);rep(i,1,n)read(a[i]);
	rep(i,1,n){
		int j=i;while(j+1<=n&&a[j+1]==a[i])j++;
		Vp b;rep(k,i,j)b.pb(Pii(1,1));Set[Pii(i,a[i])]=b;//Set.insert(pair<Pii,Vp>(Pii(i,a[i]),b));
		heap.insert(Pii(a[i],i));i=j;
	}
	while(!Set.empty()){
		Pii tmp=*heap.begin();heap.erase(heap.begin());
		if(tmp.fi==inf)break;
		map<Pii,Vp>::iterator it=Set.find(Pii(tmp.se,tmp.fi)),it1;
	//	cerr<<(*it).fi.fi<<' '<<res<<endl;
		if(SZ((*it).se)<l){
			res+=calc((*it).se);
			int pos=(*it).fi.fi;
			Set.erase(it);Set.insert(pair<Pii,Vp>(Pii(pos,inf),{}));heap.insert(Pii(inf,pos));
			continue;
		}
		res+=calc((*it).se);
		Vp b(SZ((*it).se)/l,Pii(0,0));
		rep(i,l-1,SZ((*it).se)-1)b[(i+1)/l-1].se+=(*it).se[i].se;
		int pos=SZ(b)-1,cnt=0;per(i,SZ((*it).se)-l,0){
			cnt++;if(cnt>l)cnt-=l,pos--;
			b[pos].fi+=(*it).se[i].fi;
		}
		pos=(*it).fi.fi;int val=(*it).fi.se+1;Set.erase(it);
		it=Set.insert(pair<Pii,Vp>(Pii(pos,val),b)).fi;heap.insert(Pii(val,pos));
		res-=calc((*it).se);
		it1=it;it1++;merge_front(it);if(it1!=Set.end())merge_front(it1);
	}
	cout<<res;
	return 0;
}
