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;
const int N=500005,inf=0x3f3f3f3f;
int read(){
	int f=1,g=0;
	char ch=getchar();
	for (;!isdigit(ch);ch=getchar()) if (ch=='-') f=-1;
	for (;isdigit(ch);ch=getchar()) g=g*10+ch-'0';
	return f*g;
}
int n,m,L,cnt,h[N],b[N],sl[N],sr[N];
ll ans;
typedef pair<int,int> pr;
priority_queue<pr,vector<pr>,greater<pr> > f;
struct node{int val,l,r,pre,nex,col;}a[N];
int getsum(int *s,int l,int r){return s[r]-s[l-1];}
void split(int x){
	int cur=x;m=0;
	while (a[x].val==a[cur].val){
		b[++m]=cur;
		sl[m]=sl[m-1]+a[cur].l;
		sr[m]=sr[m-1]+a[cur].r;
		cur=a[cur].nex;
	}
}
int getpre(int x){while(a[a[x].pre].val==a[x].val) x=a[x].pre;return x;}
void recalc(){
	for (int i=1,j=1;i<=m;i++){
		while ((j-i+1<L)||(a[b[i]].col==a[b[j]].col)) j++;
		if (j<=m) ans+=(ll)a[b[i]].l*getsum(sr,j,m);
		else break;
	}
}
void printch(int x){
	while (a[x].pre) x=a[x].pre;
	for (;x;x=a[x].nex) printf("%d ",x);
	printf("\n");
}
int main(){
	n=read();L=read();ans=cnt=n;
	for (int i=1;i<=n;i++){
		a[i].val=read();a[i].l=a[i].r=1;
		a[i].pre=i-1;a[i].nex=i+1;h[i]=1;
		f.push(make_pair(a[i].val,i));
	}
	a[n].nex=0;
	for (int i=1,j;i<=n;i=j){
		for (j=i;a[i].val==a[j].val;j++);
		int len=j-i;
		if (len>=L) ans+=(ll)(len-L+1)*(len-L+2)/2;
		while (i<j){a[i].col=j-1;i++;}
	}
	while (1){
		while (!h[f.top().second]) f.pop();
		int x=getpre(f.top().second),y;f.pop();
		//printch(x);
		if (a[x].val>=inf) break;
		split(x);
		for (int i=1;i<=m;i++) h[b[i]]=0;
		x=a[b[1]].pre,y=a[b[m]].nex;
		if (m<L){
			a[++cnt].val=inf;
			a[cnt].pre=x;a[cnt].nex=y;
			a[cnt].col=cnt;
			if (x) a[x].nex=cnt;
			if (y) a[y].pre=cnt;
			h[cnt]=1;f.push(make_pair(a[cnt].val,cnt));
			continue;
		}
		recalc();
		int r=m/L;
		for (int i=1;i<=r;i++){
			a[cnt+i].val=a[b[1]].val+1;
			int tl=m-(r-i+1)*L+1,tr=max(1,tl-(L-1));
			a[cnt+i].l=getsum(sl,tr,tl);
			tl=i*L,tr=min(m,tl+L-1);
			a[cnt+i].r=getsum(sr,tl,tr);
			a[cnt+i].pre=(i!=1) ? (cnt+i-1) : x;
			a[cnt+i].nex=(i!=r) ? (cnt+i+1) : y;
			a[cnt+i].col=cnt+r;
			h[cnt+i]=1;f.push(make_pair(a[cnt+i].val,cnt+i));
		}
		if (x) a[x].nex=cnt+1;
		if (y) a[y].pre=cnt+r;
		cnt+=r;
	}
	printf("%lld\n",ans);
	return 0;
}