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
using namespace std;
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 200010
#define ll long long
int n,m;
int a[N];
struct Node{
	Node *pre,*suc;
	int v,L,R;
	ll s;
	bool f;
} *fir,*lst;
Node *ins(int v,int L,int R,int s,Node *pre,Node *suc){
	Node *nw=new Node;
	*nw=(Node){pre,suc,v,L,R,s,0};
	if (pre) pre->suc=nw;
	if (suc) suc->pre=nw;
	return nw;
}
Node *h[N];
int nh;
bool cmph(Node *son,Node *fa){return son->v>fa->v;}
int L[N],R[N],L_[N],R_[N];
ll calc(int L[],int R[],int k){
	ll sL=0,s=0;
	for (int i=1;i<=k;++i){
		if (i-m+1>0)
			sL+=L[i-m+1];
		s+=(sL+L[i])*R[i];
	}
	return s;
}
ll ans;
int main(){
//	freopen("in.txt","r",stdin);
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;++i)
		scanf("%d",&a[i]);
	ans=n;
	fir=lst=ins(a[1],1,1,1,NULL,NULL);
	h[nh++]=fir,fir->f=1;
	for (int i=2;i<=n;++i){
		lst=ins(a[i],1,1,1,lst,NULL);
		if (lst->v!=lst->pre->v)
			h[nh++]=lst,lst->f=1;
	}
	make_heap(h,h+nh,cmph);
	while (nh){
		Node *fir=h[0];
		pop_heap(h,h+nh--,cmph);
		if (fir->f==0 || fir->pre && fir->pre->v==fir->v)
			continue;
		int v=fir->v,k=0;
		Node *p=fir,*lst=p;
		for (int i=1;p && p->v==v;++i,p=p->suc)
			L[i]=p->L,R[i]=p->R,++k,lst=p;
		Node *pre=fir->pre,*suc=lst->suc;
		if (pre) pre->suc=NULL;
		if (suc) suc->pre=NULL;
		fir->f=0;
		fir->pre=lst->suc=NULL;
		if (k==1 || k>=m){
			for (Node *p=fir;p && p->v==v;p=p->suc)
				ans-=p->s;
			ans+=calc(L,R,k);
			if (k==1)
				continue;
			int d=k/m;
			memset(L_,0,sizeof(int)*(d+1));
			memset(R_,0,sizeof(int)*(d+1));
			for (int i=m;i<=k;++i)
				R_[i/m]+=R[i];
			for (int i=k-m+1;i>=1;--i)
				L_[d-(k-i+1)/m+1]+=L[i];
			for (int i=d;i>=1;--i)
				suc=ins(v+1,L_[i],R_[i],0,pre,suc);
			suc->f=1;
			suc->s=calc(L_,R_,d);
			h[nh++]=suc;
			push_heap(h,h+nh,cmph);
			continue;
		}
	}
	printf("%lld\n",ans);
	return 0;
}











