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
//copy from https://atcoder.jp/contests/agc037/submissions/7059910
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define mem(x,v) memset(x,v,sizeof(x))
#define Rep(i,a,b) for(register int i=(a);i<=int(b);++i)
#define rep(i,a,b) for(register int i=(a);i<int(b);++i)
#define Dep(i,a,b) for(register int i=(a);i>=int(b);--i)
#define gc getchar
#define pc putchar
#define fi first
#define se second
inline ll read(){
    ll x=0,f=1;char c=gc();
    for(;!isdigit(c);c=gc())if(c=='-')f=-1;
    for(;isdigit(c);c=gc())x=(x<<1)+(x<<3)+(c^48);
    return x*f;
}
inline void write(ll x){if(x<0)x=-x,pc('-');if(x>=10)write(x/10);putchar(x%10+'0');}
inline void writeln(ll x){write(x);pc('\n');}
inline void wri(ll x){write(x);pc(' ');}
const int maxn = 2e5+233;
int n,l,a[maxn];
pii b[maxn];
vector<pair<pii,pii> > f,g;
ll calc(vector<pii> &v){
	ll res = 0 ,sum = 0;
	for(unsigned i=0,j=l-1;j<v.size();++i,++j)
		sum+=v[i].fi,res+=sum*v[j].se;
	return res;
}
int main(){
	n = read(),l = read();
	Rep(i,1,n){
		a[i] = read();
		b[i] = make_pair(a[i],i);
	}sort(b+1,b+1+n);
	int pos = 0;
	ll res = n,val = 0;
	for(;;){
//		printf("val = %d\n",val);
		if(f.empty()){
			if(pos > n) break;
			val = b[pos].fi;
		} else ++val;
		while(val == b[pos].fi){f.push_back({{b[pos].se,b[pos].se},{1,1}});pos++;}
		g.clear();sort(f.begin(),f.end());
		for(unsigned i=0,j=i;i<f.size();i=++j){
			while(j+1<f.size()&&f[j+1].fi.fi==f[j].fi.se+1)++j;
			int len=j-i+1,cnt=len/l;
			if(cnt){
				vector<pii> tmp,ff,gg;
				Rep(k,i,j) tmp.push_back(f[k].se);
				res += calc(tmp);
				Rep(k,1,cnt){
					ff.push_back({f[i].fi.fi+k-1,(k==cnt)?f[j].fi.se:f[i].fi.fi+k-1});
					gg.push_back({0,0});
				}
				Rep(k,i,j){
					int tl=k-i+1,tr=j-k+1;
					if(tl>=l) gg[tl/l-1].se += f[k].se.se;
					if(tr>=l) gg[cnt-tr/l].fi += f[k].se.fi;
				}
				res -= calc(gg);
				rep(k,0,cnt) g.push_back({ff[k],gg[k]});
			}
		}f = g;
	}
	writeln(res);
	return 0;
}