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 db double 
#define maxn 200005 
#define mod 998244353
#define vi vector<double>
#define pb push_back
#define ll long long
#define iter set<th>::iterator
using namespace std;
ll ksm(ll a, ll b) {
	if (!b) return 1;
	ll ns = ksm(a, b >> 1);
	ns = ns * ns % mod;
	if (b & 1) ns = ns * a % mod;
	return ns;
}
inline int add(int a, int b) {
	a += b;
	return (a < mod) ? a : (a - mod);
}
inline int sub(int a, int b) {
	a -= b;
	return (a < 0) ? a + mod : a;
}
inline int mul(int a, int b) {
	return (ll)a * b % mod;
}
// head
struct th{
	int tp, pl, num, l, r;
	th(){
	}
	th(int u, int a, int b) {
		tp = u, pl = a, num = b;
		l = r = 1;
	}
	bool operator < (const th &b)const {
		if (tp == 0) return pl < b.pl;
		else  {
			if (num != b.num) return num < b.num;
			return pl < b.pl;
		}
	}
}; 
int n, l;
ll ans = 0;
set<th> ps, qs;
ll cal(vector<th> u) {
	int n = u.size();
	vi sm(n);
	sm[0] = u[0].r;
	for (int i = 1; i < n; i++)
		sm[i] = sm[i - 1] + u[i].r;
	ll ans = 0;
	for (int i = 0; i < n; i++) {
		int nx = i + l - 1;
		int ns = sm[n - 1];
		nx--;
		if (nx >= 0) ns -= sm[min(nx, n - 1)];
		ans += 1ll * u[i].l * ns;
	}
	return  ans;
}
void otp(set<th> r) {
	cout << "QQQ" << endl;
	iter q = r.begin();
	while (q != r.end()) {
		cout << (*q).pl << " " << (*q).num << endl;
		q++;
	}
}
int sum[maxn];
int main() {
	cin >> n >> l;
	int inf = 2e9;
	for (int i = 1; i <= n; i++) {
		int a;
		scanf("%d", &a);
		ps.insert(th(0, i, a)), 
		qs.insert(th(1, i, a));
	}
	ans = n;
	while(1) {
		th u1 = *qs.begin();
		if (u1.num >= inf) break;
		iter it = ps.find(th(0, u1.pl, u1.num)), ft = it;
		vector<th> ns;
		while (it != ps.end() && (*it).num == u1.num)
			ns.pb(*it), it++;
		int cnt = ns.size();
		for (int i = 0; i < cnt; i++)
			ps.erase(ns[i]), 
			qs.erase(th(1, ns[i].pl, ns[i].num));
		if (cnt < l) {
		//	ans += cnt;
			ps.insert(th(0, u1.pl, inf)), 
			qs.insert(th(1, u1.pl, inf));
		}
		else {
			vector<th> gr(cnt / l);
			ans += cal(ns);
			int pl = 0;
			for (int i = 0; i < cnt / l; i++) {
				gr[i] = th(1, ns[pl].pl, ns[pl].num + 1);
				gr[i].l = gr[i].r = 0;
				for (int j = pl + l - 1; j < min(pl + 2 * l - 1, cnt); j++)	
					gr[i].r += ns[j].r;
				pl += l;
			}
			pl = cnt - 1;
			for (int i = cnt / l - 1; i >= 0; i--) {
				for (int j = pl - l + 1; j >= max(0, pl - 2 * l + 2); j--)
					gr[i].l += ns[j].l; 
				pl -= l;
			}
			ans -= cal(gr);
			for (int i = 0; i < cnt / l; i++) {
				qs.insert(gr[i]);
				gr[i].tp = 0, ps.insert(gr[i]);
			}
		}
	
	//	otp(ps);
		//otp(qs);
	//	cout << ans << endl;
	////	system("pause");
	}
	cout << ans << endl;
	return 0;
}
