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 vector<int>V;
typedef long long ll;
const int N=2e5+5;
long long ans;
int n,L,a[N],i,j,x,aa[N];
int g[N];
V lv[N],rv[N];int mx[N];
int gfa(int x){return g[x]==x?x:g[x]=gfa(g[x]);}
inline bool cmp(int x,int y){return a[x]==a[y]?x<y:a[x]<a[y];}
long long mi;
struct atom{
	V l,r;int mx;bool full;
	inline void set(const atom&a,int mx2){
		ll z=1;int zz=max(a.l.empty()?0:a.l.back(),a.r.empty()?0:a.r[0]);
		full=0;l.clear();r.clear();
		for(mx=a.mx;mx<mx2 && z<=zz;z*=L,++mx);
		if(zz<z){mx=mx2;return;}
		full=a.full;
		for(int x:a.l)if(x>=z)l.push_back(x/z);
		for(int x:a.r)if(x>=z)r.push_back(x/z);
	}
}b[N],v[N];int xb;
int w,l,s,st[N];bool bb[N];
inline void uni(atom&zz){
	w=s=0;l=1;
	zz.full=1;zz.mx=b[1].mx;
	for(int i=1;i<=xb;++i){
		zz.full&=b[i].full;
		for(int x:b[i].l){
			for(;l<=w && st[l]+s+x>=L;++l)if(l<w && bb[l+1])s-=st[l+1];
			ans+=l-1;
		}
		if(!b[i].full)w=s=0,l=1;
		if(!b[i].r.empty()){
			if(l<=w)s+=b[i].r[0];int ow=w;
			for(int x:b[i].r)st[++w]=x,bb[w]=0;bb[ow+1]=1;
		}
	}
	zz.r.resize(w);s=0;for(int i=w;i;--i)zz.r[i-1]=st[i]+s,s+=bb[i]?st[i]:0;
	w=0;
	for(int i=xb;i;--i){
		if(!b[i].full)w=0;
		if(!b[i].l.empty()){
			int ow=w;reverse(b[i].l.begin(),b[i].l.end());
			for(int x:b[i].l)st[++w]=x,bb[w]=0;bb[ow+1]=1;
		}
	}
	zz.l.resize(w);s=0;for(int i=w;i;--i)zz.l[w-i]=st[i]+s,s+=bb[i]?st[i]:0;
}
int main(){
	ios::sync_with_stdio(0);cin.tie(0);
	cin>>n>>L;for(i=1;i<=n;++i)cin>>a[i],aa[i]=i,g[i]=i,v[i].l=v[i].r={1},v[i].mx=a[i],v[i].full=1;
	std::sort(aa+1,aa+n+1,cmp);
	for(i=1;i<=n;i=j){
		xb=0;
		if(aa[i]>1 && a[aa[i]-1]<a[aa[i]])b[++xb].set(v[aa[i]-1],a[aa[i]]),g[aa[i]-1]=aa[i];
		for(j=i+1,b[++xb]=v[aa[i]];j<=n && a[aa[j]]==a[aa[i]] && gfa(aa[j-1]+1)>=aa[j]-1
			 && a[aa[j-1]+1]<=a[aa[i]];++j){
			if(aa[j-1]+1<aa[j])b[++xb].set(v[aa[j]-1],a[aa[i]]),g[aa[j]-1]=aa[j];
			b[++xb]=v[aa[j]];g[aa[j-1]]=aa[j-1]+1;
		}
		if(aa[j-1]<n && a[aa[j-1]]>a[aa[j-1]+1])b[++xb].set(v[gfa(aa[j-1]+1)],a[aa[i]]),g[aa[j-1]]=aa[j-1]+1;
		uni(v[gfa(aa[i])]);
	}
	cout<<ans+n<<endl;
	return 0;
}