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>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
#define mp make_pair
#define PI pair<int,int>
#define poly vector<ll>
#define For(i,l,r) for(int i=(int)(l);i<=(int)(r);i++)
#define Rep(i,r,l) for(int i=(int)(r);i>=(int)(l);i--)
#define pb push_back
#define fi first
#define se second
inline char gc(){
    static char buf[100000],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
#define gc getchar
inline ll read(){
	ll x = 0; char ch = gc(); bool positive = 1;
	for (; !isdigit(ch); ch = gc())	if (ch == '-')	positive = 0;
	for (; isdigit(ch); ch = gc())	x = x * 10 + ch - '0';
	return positive ? x : -x;
}
inline void write(ll a){
    if(a<0){
    	a=-a; putchar('-');
	}
    if(a>=10)write(a/10);
    putchar('0'+a%10);
}
inline void writeln(ll a){write(a); puts("");}
inline void wri(ll a){write(a); putchar(' ');}
inline ull rnd(){
	return ((ull)rand()<<30^rand())<<4|rand()%4;
}
const int N=200005;
int k,A[N],lx[N],rx[N],a[N],nxt[N],pre[N];
ll ycl[N];
priority_queue<PI,vector<PI>,greater<PI> > q;
ll solve(int l,int r){
	r=nxt[r];
	int dq=l;
	ll ans=0;
	int sum=0;
	For(i,1,k-1){dq=nxt[dq]; ans++; if(dq==r)return ans;}
	while(dq!=r){
		sum+=lx[l]; l=nxt[l]; 
		ans+=(ll)sum*rx[dq]+1;
		dq=nxt[dq];
	}
	return ans;
}
int main(){
	int n=read(); k=read();
	For(i,k,n)ycl[i]=ycl[i-1]+(i-k+1);
	For(i,1,n){
		a[i]=read(); lx[i]=1; rx[i]=1;
	}
	nxt[0]=1; pre[n+1]=n;
	For(i,1,n){pre[i]=i-1; nxt[i]=i+1; q.push(mp(a[i],i)); }
	//For(i,1,n)wri(ycl[i]); puts("");
	ll ans=0;
	while(q.size()){
		PI t=q.top();  q.pop();
		int l=t.se,r=l,cnt=1;
		while(a[nxt[r]]==a[l]){r=nxt[r]; cnt++; q.pop(); } 
		//cout<<q.size()<<" "<<cnt<<" "<<t.fi<<" "<<t.se<<" "<<l<<" "<<r<<" "<<" "<<ycl[cnt]<<endl;
		l=pre[l]; r=nxt[r];
		ans+=solve(nxt[l],pre[r]);
		if(cnt<k)continue;
		int zs=cnt,jb=l;
		zs-=k; For(i,1,k)jb=nxt[jb];
		For(i,1,cnt/k){
			int meiju=min(k,zs+1);
			rx[l+i]=0; For(j,1,meiju){rx[l+i]+=rx[jb]; jb=nxt[jb];} zs-=k;
		}
		zs=cnt-k; jb=r; For(i,1,k)jb=pre[jb];
		Rep(i,cnt/k,1){
			int meiju=min(k,zs+1);
			A[i]=0; For(j,1,meiju){A[i]+=lx[jb]; jb=pre[jb];} zs-=k;
		}
		For(i,1,cnt/k)lx[l+i]=A[i];
		For(i,1,cnt/k){nxt[l+i]=l+i+1; pre[l+i]=l+i-1; a[l+i]=t.fi+1; q.push(mp(a[l+i],l+i));}
		nxt[l]=l+1; pre[r]=l+cnt/k; nxt[l+cnt/k]=r;
		//cout<<ans<<endl;
		ans-=solve(nxt[l],pre[r]);
		//For(i,1,cnt/k)wri(lx[l+i]); puts("");
		//cout<<ans<<" "<<nxt[jb]<<" "<<pre[r]<<endl;
	}
	cout<<ans<<endl;
}