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
#define ull unsigned ll
#define uint unsigned
#define pii pair<int,int>
#define pll pair<ll,ll>
#define PB push_back
#define fi first
#define se second
#define For(i,j,k) for (int i=(int)(j);i<=(int)(k);i++)
#define Rep(i,j,k) for (int i=(int)(j);i>=(int)(k);i--)
#define CLR(a,v) memset(a,v,sizeof(a));
#define CPY(a,b) memcpy(a,b,sizeof(a));
using namespace std;
const int N=200005;
priority_queue<pii,vector<pii>,greater<pii> > Q;
int pre[N],suf[N],q[N];
int a[N],l[N],r[N],n,L;
int Sl[N],Sr[N];
ll ans;
void erase(int x){
	suf[pre[x]]=suf[x];
	pre[suf[x]]=pre[x];
}
void work(){
	//printf("work %d %d\n",*q,ans);
	//For(i,1,*q) printf("%d %d %d\n",q[i],l[i],r[i]); puts("");
	int m=*q,pl,pr;
	q[0]=pre[q[1]];
	q[m+1]=suf[q[m]];
	Sl[0]=Sr[m+1]=0;
	For(i,1,m+1) Sl[i]=Sl[i-1]+l[q[i]];
	Rep(i,m,0) Sr[i]=Sr[i+1]+r[q[i]];
	For(i,L,m) ans+=1ll*r[q[i]]*Sl[i-L+1];
	pl=m+1,pr=max(1,m-L+2);
	Rep(i,m/L,1){
		pl-=L; pr=max(1,pr-L);
		l[q[i]]=Sl[pl]-Sl[pr-1];
	}
	pl=0,pr=min(m,L-1);
	For(i,1,m/L){
		pl+=L; pr=min(m,pr+L);
		r[q[i]]=Sr[pl]-Sr[pr+1];
	}
	if (m<L){
		For(i,2,m) erase(q[i]);
		a[q[1]]=1<<30;
		Q.push(pii(a[q[1]],q[1]));
	}
	else{
		For(i,1,m/L) ++a[q[i]];
		For(i,1,m/L) Q.push(pii(a[q[i]],q[i]));
		For(i,m/L+1,m) erase(q[i]);
		For(i,1,m/L) Sl[i]=Sl[i-1]+l[q[i]];
		For(i,L,m/L) ans-=1ll*r[q[i]]*Sl[i-L+1];
	}
}
int main(){
	scanf("%d%d",&n,&L);
	For(i,1,n) scanf("%d",&a[i]);
	For(i,1,n) l[i]=r[i]=1;
	For(i,1,n) pre[i]=i-1,suf[i]=i+1;
	For(i,1,n) Q.push(pii(a[i],i));
	while (!Q.empty()){
		q[++*q]=Q.top().se; Q.pop();
		if (a[q[1]]==1<<30) break;
		for (;!Q.empty()&&Q.top().fi==a[q[*q]];){
			int tmp=Q.top().se; Q.pop();
			if (tmp!=suf[q[*q]]) work(),*q=0;
			q[++*q]=tmp;
		}
		work(); *q=0;
	}
	printf("%lld\n",ans+n);
}