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 <vector>
#include <cassert>
#include <cstring>
#include <algorithm>
#define meow(args...) fprintf(stderr, args)

typedef std::pair<int, int> pair;
struct Element {
	int l, r;
	pair v;
	bool operator<(const Element &o) const {return l<o.l;}
};

const int N=2e5;

int n, l, x[N];
pair y[N];

template<class T1, class T2> inline bool cmin(T1 &a, const T2 &b) {return b<a?(a=b, true):false;}
template<class T1, class T2> inline bool cmax(T1 &a, const T2 &b) {return a<b?(a=b, true):false;}
int read() {
	int a=0;
	unsigned char c;
	while((c=getchar()-'0')>9);
	while(a=a*10+c, (c=getchar()-'0')<=9);
	return a;
}
long long calc(std::vector<pair> jar) {
	int len=jar.size();
	long long ans=0, lsum=0;
	for(int i=l-1; i<len; ++i) {
		lsum+=jar[i-l+1].first;
		ans+=lsum*jar[i].second;
	}
	return ans;
}
int main() {
	n=read(), l=read();
	std::generate(x, x+n, read);
	for(int i=0; i<n; ++i) y[i]=pair(x[i], i);
	std::sort(y, y+n);

	int m=0;
	pair *pos=y;
	long long ans=n;
	std::vector<Element> a, b;
	while(true) {
		if(a.empty()) {
			if(pos==y+n) break;
			m=pos->first;
		} else ++m;
		for(; pos->first==m; ++pos) a.push_back({pos->second, pos->second+1, pair(1, 1)});
		std::sort(a.begin(), a.end());
		b.clear();
		for(int i=0, j=0; i<a.size(); i=j) {
			while(++j<a.size()&&a[j-1].r==a[j].l);
			int len=j-i, cnt=len/l;
			if(cnt!=0) {
				std::vector<pair> cur, val(cnt);
				for(int k=i; k<j; ++k) cur.push_back(a[k].v);
				for(int k=i; k<j; ++k) {
					int tl=k-i+1, tr=j-k;
					if(tl>=l) val[tl/l-1].second+=a[k].v.second;
					if(tr>=l) val[cnt-tr/l].first+=a[k].v.first;
				}
				ans+=calc(cur)-calc(val);
				for(int k=0; k<cnt; ++k) b.push_back({a[i].l+k, a[i].l+k+1, val[k]});
				b.back().r=a[j-1].r;
			}
		}
		a=b;
	}
	printf("%lld\n", ans);
	return 0;
}
