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
/*
Author: QAQAutomaton
Lang: C++
Code: F.cpp
Mail: lk@qaq-am.com
Blog: https://www.qaq-am.com/
*/
#include<bits/stdc++.h>
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define DEBUG printf("Passing [%s] in LINE %d\n",__FUNCTION__,__LINE__)
#define Debug debug("Passing [%s] in LINE %d\n",__FUNCTION__,__LINE__)
#define all(x) x.begin(),x.end()
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef complex<double> cp;
typedef pair<int,int> pii;
int inf;
const double eps=1e-8;
const double pi=acos(-1.0);
template<class T,class T2>int chkmin(T &a,T2 b){return a>b?a=b,1:0;}
template<class T,class T2>int chkmax(T &a,T2 b){return a<b?a=b,1:0;}
template<class T>T sqr(T a){return a*a;}
template<class T,class T2>T mmin(T a,T2 b){return a<b?a:b;}
template<class T,class T2>T mmax(T a,T2 b){return a>b?a:b;}
template<class T>T aabs(T a){return a<0?-a:a;}
template<class T>int dcmp(T a,T b){return a>b;}
template<int *a>int cmp_a(int x,int y){return a[x]<a[y];}
#define min mmin
#define max mmax
#define abs aabs
struct __INIT__{
	__INIT__(){
		memset(&inf,0x3f,sizeof(inf));
	}
}__INIT___;
namespace io {
	const int SIZE = (1 << 21) + 1;
	char ibuf[SIZE], *iS, *iT, obuf[SIZE], *oS = obuf, *oT = oS + SIZE - 1, c, qu[55]; int f, qr;
	// getchar
	#define gc() (iS == iT ? (iT = (iS = ibuf) + fread (ibuf, 1, SIZE, stdin), (iS == iT ? EOF : *iS ++)) : *iS ++)
	// print the remaining part
	inline void flush () {
		fwrite (obuf, 1, oS - obuf, stdout);
		oS = obuf;
	}
	// putchar
	inline void putc (char x) {
		*oS ++ = x;
		if (oS == oT) flush ();
	}
	template<typename A>
	inline bool read (A &x) {
		for (f = 1, c = gc(); c < '0' || c > '9'; c = gc()) if (c == '-') f = -1;else if(c==EOF)return 0;
		for (x = 0; c <= '9' && c >= '0'; c = gc()) x = x * 10 + (c & 15); x *= f;
		return 1;
	}
	inline bool read (char &x) {
		while((x=gc())==' '||x=='\n' || x=='\r');
		return x!=EOF;
	}
	inline bool read(char *x){
		while((*x=gc())=='\n' || *x==' '||*x=='\r');
		if(*x==EOF)return 0;
		while(!(*x=='\n'||*x==' '||*x=='\r'||*x==EOF))*(++x)=gc();
		*x=0;
		return 1;
	}
	template<typename A,typename ...B>
	inline bool read(A &x,B &...y){
		return read(x)&&read(y...);
	}
	template<typename A>
	inline bool write (A x) {
		if (!x) putc ('0'); if (x < 0) putc ('-'), x = -x;
		while (x) qu[++ qr] = x % 10 + '0',  x /= 10;
		while (qr) putc (qu[qr --]);
		return 0;
	}
	inline bool write (char x) {
		putc(x);
		return 0;
	}
	inline bool write(const char *x){
		while(*x){putc(*x);++x;}
		return 0;
	}
	inline bool write(char *x){
		while(*x){putc(*x);++x;}
		return 0;
	}
	template<typename A,typename ...B>
	inline bool write(A x,B ...y){
		return write(x)||write(y...);
	}
	//no need to call flush at the end manually!
	struct Flusher_ {~Flusher_(){flush();}}io_flusher_;
}
using io :: read;
using io :: putc;
using io :: write;
int a[200005],cur,is[200005],pw[200005],fa[200005];
int *pre[200005],*suf[200005],cnt[200005],nwa[200005];
ll ans;
int dp[600005],*f=dp+400000;
int w[25000005],*at=w;
pii b[200005];
int *newI(int n){
	at+=n;
	return at-n;
}
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
int nex[200005],stk[400005],tp,ist[200005];
void add(int x,int y){
//	write(x,'-',y,'\n');
	if(!ist[x]){stk[++tp]=x;}
	if(!ist[y]){stk[++tp]=y;}
	ist[y]=-1;if(!ist[x])ist[x]=1;	
	nex[x]=y;
}
int id[200005],m,n,l;
void upd(int x){
	if(!is[x])return;
	x=find(x);
	if(nwa[x]!=cur){
		int S=pw[min(cur-nwa[x],n)];
		int *p=pre[x],*s=suf[x];
		for(int j=1;j<=cnt[x];++j){
			int w=p[j-1];
			p[j-1]=0;
			if(j>=S)p[j/S-1]+=w;
			w=s[j-1];
			s[j-1]=0;
			if(j>=S)s[j/S-1]+=w;
		}
		cnt[x]/=S;
		nwa[x]=cur;
		if(!cnt[x]){
			int y=x;
			while(is[--y])is[y]=0;
			y=x;while(is[++y])is[y]=0;
			is[x]=0;
		}
	}
}
void put(int x){
	upd(x-1);
	upd(x+1);
	is[x]=1;
	nwa[x]=a[x];
	cnt[x]=1;
	pre[x]=newI(1);pre[x][0]=1;suf[x]=newI(1);suf[x][0]=1;
	fa[x]=x;
	if(is[x-1]){add(find(x-1),x);}
	if(is[x+1]){add(x,find(x+1));}
}
void solve(){
	int cc=0;
	for(int i=1;i<=m;++i){

		cc+=cnt[id[i]];
	}	

/*	write(m,'\n');
	for(int i=1;i<=m;++i){
		write(cnt[id[i]],':');
		for(int j=0;j<cnt[id[i]];++j)write(pre[id[i]][j],' ');
		write('|');
		for(int j=0;j<cnt[id[i]];++j)write(pre[id[i]][j],' ');
		write('\n');
	}*/
	int *np=newI(cc),*ns=newI(cc);
	int t=0;
	for(int i=1;i<=m;++i){
		for (int j=0;j<cnt[id[i]];++j){
			np[t]=pre[id[i]][j];
			++t;
		}
	}
	t=0;
	for(int i=m;i;--i){
		for (int j=0;j<cnt[id[i]];++j){
			ns[t]=suf[id[i]][j];
			++t;
		}
	}
	for(int i=m;i;--i){
		for(int j=1;j<=cnt[id[i]];++j)ans+=(ll)suf[id[i]][j-1]*f[max(1,l-j)];
		for(int j=cnt[id[i]];j;--j){f[0]=f[1]+pre[id[i]][j-1];--f;}
	}
	for(int i=1;i<=cc;++i)*(++f)=0;
	/*write(ans,'\n');
	write(cc,'|',id[1],'\n');*/
	cnt[id[1]]=cc;
	pre[id[1]]=np;
	suf[id[1]]=ns;
}
void work(){
	for(;tp;--tp){
		if(ist[stk[tp]]<=0){ist[stk[tp]]=0;continue;}
		ist[stk[tp]]=0;
		int at=stk[tp];
		m=0;
		while(at){
//			write(at,'(');
			id[++m]=at;
			fa[at]=stk[tp];
			int nx=nex[at];
			nex[at]=0;
			at=nx;
		}
		solve();
	}
}
signed main(){
#ifdef QAQAutoMaton 
	freopen("F.in","r",stdin);
	freopen("F.out","w",stdout);
#endif
	read(n,l);
	pw[0]=1;
	int iee=n/l+1;
	for(int i=1;i<=n;++i)pw[i]=min(pw[i-1],iee)*l;
	for(int i=1;i<=n;++i){read(a[i]);b[i]=make_pair(a[i],i);}
	sort(b+1,b+n+1);
	for(int i=1,j=1;i<=n;i=j){
		cur=b[i].x;
		while(b[i].x==b[j].x){put(b[j].y);++j;}
		work();
	}
	write(ans+n,'\n');
	return 0;
}


