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 <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#define PB push_back
#define ll long long
using namespace std;
template <class T>
inline void rd(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-'0'+c,c=getchar(); x*=f;
}

const int N=6e5+10,inf=2e9;
int fa[N],ch[N][2],mx[N],mi[N],sz[N],val[N],ncnt,rt;
int Lx[N],Rx[N],vis[N];
int L;
inline void push_up(int c) {
	if(c==0) printf("!!!\n");
	sz[c]=sz[ch[c][0]]+sz[ch[c][1]]+1;
	mi[c]=min(min(mi[ch[c][0]],mi[ch[c][1]]),vis[c]?inf:val[c]);
	mx[c]=max(max(mx[ch[c][0]],mx[ch[c][1]]),vis[c]?0:val[c]);
}
inline bool get(int x) { return ch[fa[x]][1]==x; }
inline void rotate(int x) {
	int f=fa[x],ff=fa[f],d=get(x);
	fa[x]=ff; if(ff) ch[ff][ch[ff][1]==f]=x;
	fa[ch[x][d^1]]=f,ch[f][d]=ch[x][d^1];
	fa[f]=x,ch[x][d^1]=f; push_up(f),push_up(x);
}
void splay(int x,int gl) {
	for(int f=fa[x];f!=gl;rotate(x),f=fa[x])
		if(fa[f]!=gl) rotate(get(x)==get(f)?f:x);
	if(!gl) rt=x;
}
int kth(int x,int k) {
//	cout<<"kth:"<<x<<' '<<sz[x]<<' '<<sz[ch[x][0]]<<' '<<k<<endl;
	if(sz[ch[x][0]]+1==k) return x;
	if(k<=sz[ch[x][0]]) return kth(ch[x][0],k);
	return kth(ch[x][1],k-sz[ch[x][0]]-1);
}
void debug(int x) {
	if(!x) return;
	debug(ch[x][0]);
	printf("%d ",vis[x]?-1:val[x]);
	debug(ch[x][1]);
	push_up(x);
}
void Debug() { printf("debug:"),debug(rt),puts(""); sz[0]=0; }
int split(int l,int r) {
//	if(l==1&&r==sz[rt]) return rt;
//	if(l==1) {
//		int y=kth(rt,r+1); splay(y,0);
//		return ch[y][0];
//	}
//	if(r==sz[rt]) {
//		int x=kth(rt,l-1); splay(x,0);
//		return ch[x][1];
//	}
//	cout<<"KTH:"<<rt<<' '<<sz[rt]<<endl;
	int x=kth(rt,l-1),y=kth(rt,r+1);
//	cout<<"SPLIT:"<<x<<' '<<y<<' '<<l-1<<' '<<r+1<<' '<<endl;
	splay(x,0),splay(y,x);
	return ch[y][0];
}
int lv[N],rv[N],V[N],Vi[N],lim;
void build(int l,int r,int &c,int f) {
	if(l>r) return (void)(c=0);
	int mid=l+r>>1; c=++ncnt;
	val[c]=V[mid],vis[c]=Vi[mid],fa[c]=f;
	Lx[c]=lv[mid],Rx[c]=rv[mid];
	build(l,mid-1,ch[c][0],c);
	build(mid+1,r,ch[c][1],c);
	push_up(c);
}
struct item {
	int p,l,r;
	item(int p=0,int l=0,int r=0): p(p),l(l),r(r) {}
};
vector<item> A;
void find(int x,int pr) {
	if(mi[x]>lim) return;
	find(ch[x][0],pr); pr+=sz[ch[x][0]];
	if(val[x]==lim&&!vis[x]) A.PB(item(pr+1,Lx[x],Rx[x]));
	find(ch[x][1],pr+1);
}

int main() {
	mi[0]=inf;
	int n; rd(n),rd(L);
	for(int i=1;i<=n;++i) rd(V[i]),lv[i]=rv[i]=1;
	Vi[0]=Vi[n+1]=1;
	build(0,n+1,rt,0);
	Vi[0]=Vi[n+1]=0;
	ll ans=0;
	while(true) {
//		cout<<rt<<' '<<mi[rt]<<' '<<mx[rt]<<endl;
		A.clear(),lim=mi[rt],find(rt,0);
//		for(int i=0;i<A.size();++i) printf("(%d,%d,%d) ",A[i].p,A[i].l,A[i].r); puts("");
//		cout<<"OK"<<endl;
		for(int l=0,r;l<A.size();l=r+1) {
			r=l; while(r+1<A.size()&&A[r+1].p==A[r].p+1) ++r;
			ll s=0;
			for(int i=l;i<=r;++i) {
				if(i-L+1>=l) s+=A[i-L+1].l;
				ans+=s*A[i].r;
				ans+=A[i].l*A[i].r;
			}
		}
		if(mi[rt]>=mx[rt]) break;
		int pre=0;
		for(int l=0,r;l<A.size();l=r+1) {
			r=l; while(r+1<A.size()&&A[r+1].p==A[r].p+1) ++r;
			int len=(r-l+1)/L;
			int u=split(A[l].p+pre,A[r].p+pre);
			pre-=r-l+1; pre+=max(len,1);
//			cout<<"fa:"<<A[l].p<<' '<<A[r].p<<' '<<u<<' '<<fa[u]<<' '<<fa[fa[u]]<<endl;
			if(!len) {
				vis[u]=1;
				ch[u][0]=ch[u][1]=0;
//				cout<<"PUSH:"<<u<<' '<<fa[u]<<' '<<rt<<endl;
				push_up(u),push_up(fa[u]),push_up(rt);
				continue;
			}
			for(int i=0;i<len;++i) lv[i]=rv[i]=0,V[i]=lim+1;
			for(int i=l+L-1;i<=r;++i) rv[(i-l+1)/L-1]+=A[i].r;
			for(int i=l;i<=r-L+1;++i) lv[len-(r-i+1)/L]+=A[i].l;
//			for(int i=0;i<len;++i) printf("(%d,%d) ",lv[i],rv[i]); puts("");
			for(int i=0,s=0;i<len;++i) {
				if(i-L+1>=0) s+=lv[i-L+1];
				ans-=s*rv[i];
				ans-=lv[i]*rv[i];
			}
			build(0,len-1,ch[fa[u]][0],fa[u]);
			push_up(fa[u]),push_up(rt);
//			cout<<"PUSH:"<<fa[u]<<' '<<rt<<endl;
		}
//		cout<<ans<<' '<<sz[rt]<<endl;
//		Debug();
	}
	printf("%lld",ans);
	return 0;
}