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>
#define clr(x) memset(x,0,sizeof x)
#define For(i,a,b) for (int i=(a);i<=(b);i++)
#define Fod(i,b,a) for (int i=(b);i>=(a);i--)
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
#define fi first
#define se second
#define outval(x) cerr<<#x" = "<<x<<endl
#define outtag(x) cerr<<"-----------------"#x"-----------------\n"
#define outarr(a,L,R) cerr<<#a"["<<L<<".."<<R<<"] = ";\
                    For(_x,L,R) cerr<<a[_x]<<" ";cerr<<endl;
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair <int,int> pii;
LL read(){
    LL x=0,f=0;
    char ch=getchar();
    while (!isdigit(ch))
        f=ch=='-',ch=getchar();
    while (isdigit(ch))
        x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    return f?-x:x;
}
const int N=200005;
int n,L;
int a[N];
int rp[N];
vector <int> vl[N],vr[N];
map <int,vector <int> > pos;
set <int> S;
vector <int> v,v2,tl,tr;
int vis[N];
int main(){
	n=read(),L=read();
	For(i,1,n){
		a[i]=read();
		pos[a[i]].pb(i);
		S.insert(a[i]);
	}
	LL ans=n;
	int k=0;
	while (!S.empty()){
		k++;

//	outtag();outval(k);
		if (k==*S.begin())
			S.erase(S.begin());
		for (auto i : pos[k]){
			rp[i]=i;
			vl[i].pb(1),vr[i].pb(1);
			v.pb(i);

//	printf("new[%d]: pos = [%d..%d]\n",i,i,rp[i]);outarr(vl[i],0,(int)vl[i].size()-1);outarr(vr[i],0,(int)vr[i].size()-1);
		}
		if (v.empty()){
			assert(!S.empty());
			k=*S.begin()-1;
			continue;
		}
		sort(v.begin(),v.end());
		int las=v[0];
		v2.clear();
		tl.clear(),tr.clear();
		tr.pb(0);
		#define tls (int)tl.size()
		#define trs (int)tr.size()
		For(_,0,(int)v.size()-1){
			int i=v[_];
			vl[i].pb(0);
			For(j,0,(int)vl[i].size()-2){
				vl[i][j]-=vl[i][j+1];
				ans+=(LL)vl[i][j]*tr[max(trs-max(L-(j+1),1),0)];
				tl.pb(vl[i][j]);
			}

//	printf("i = %d, ans = %lld\n",i,ans);
			int tmp=tr.back();
			Fod(j,(int)vr[i].size()-1,0)
				tr.pb(vr[i][j]+tmp);
			if (_==(int)v.size()-1||v[_+1]!=rp[i]+1){
				rp[las]=rp[i];

//	outarr(tl,0,tls-1);	outarr(tr,0,trs-1);
				Fod(i,trs-1,1)
					tr[i]-=tr[i-1];
				vl[las]=tl;
				vr[las].clear();
				Fod(i,trs-1,1)
					vr[las].pb(tr[i]);

//	outarr(vl[las],0,(int)vl[las].size()-1);outarr(vr[las],0,(int)vr[las].size()-1);
				For(i,0,(int)vl[las].size()-1){
					int tmp=vl[las][i];
					vl[las][i]=0;
					vl[las][(i+1)/L]+=tmp;
				}
				vl[las][0]=0;
				For(i,0,(int)vl[las].size()-2)
					vl[las][i]=vl[las][i+1],vl[las][i+1]=0;
				while (!vl[las].empty()&&!vl[las].back())
					vl[las].pop_back();
				Fod(i,(int)vl[las].size()-1,1)
					vl[las][i-1]+=vl[las][i];
				For(i,0,(int)vr[las].size()-1){
					int tmp=vr[las][i];
					vr[las][i]=0;
					vr[las][(i+1)/L]+=tmp;
				}
				vr[las][0]=0;
				For(i,0,(int)vr[las].size()-2)
					vr[las][i]=vr[las][i+1],vr[las][i+1]=0;
				while (!vr[las].empty()&&!vr[las].back())
					vr[las].pop_back();
				Fod(i,(int)vr[las].size()-1,1)
					vr[las][i-1]+=vr[las][i];

//	printf("new[%d]: pos = [%d..%d]\n",las,las,rp[las]);outarr(vl[las],0,(int)vl[las].size()-1);outarr(vr[las],0,(int)vr[las].size()-1);
				if (!vl[las].empty())
					v2.pb(las);
				if (_!=(int)v.size()-1){
					las=v[_+1];
					tl.clear(),tr.clear();
					tr.pb(0);
				}
			}
		}
		v=v2;
	}
	cout<<ans<<endl;
	return 0;
}
/*

5 2
3 2 2 2 2 

*/