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;

#define N 200020
typedef long long ll;

int n, L, a[N];

struct data {
	int le, ri, lv, rv;
	data(int le = 0, int ri = 0, int lv = 0, int rv = 0):le(le), ri(ri), lv(lv), rv(rv) {}
	bool operator < (const data &a) const {return le < a.le;}
};

typedef pair<int, int>  pii;
set<data> S;

ll calc(vector<data> &v) {
	ll sum = 0;
	ll rlt = 0;
	for (int i = 0; i < v.size(); i ++) {
		sum += v[i].lv;
		if (i + L <= v.size()) rlt += sum * v[i+L-1].rv;
	}
	return rlt;
}

int main() {
	ios_base::sync_with_stdio(0);cin.tie(0); cout.tie(0);
	cin>>n>>L;
	vector<pii> pos;
	for (int i = 1; i <= n; i ++) {
		cin>>a[i];
		pos.emplace_back(a[i], i);
	}
	sort(pos.begin(), pos.end());
	int now = 1;
	int cur = 0;
	ll ans = n;
	while (1) {
		if (S.empty()) {
			if (cur >= pos.size()) break;
			now = pos[cur].first;
		}
        while (cur < pos.size() && pos[cur].first == now) {
			S.insert(data(pos[cur].second, pos[cur].second, 1, 1));
			cur ++;
        }
        vector<data> all;
        while (!S.empty()) {
			set<data>::iterator it = S.begin();
			vector<data> tmp = {*it};
			S.erase(*it);
			while (!S.empty() && S.begin()->le == tmp.back().ri + 1) {
				tmp.push_back(*S.begin());
				S.erase(*S.begin());
			}
			if (tmp.size() >= L) {
				ans += calc(tmp);
				int c = tmp.size() / L;
				vector<data> nw = tmp;
				nw.resize(c);
				for (int i = 0; i < c; i ++) {
					nw[i].le = tmp[0].le + i;
					if (i < c - 1) nw[i].ri = nw[i].le;
					else nw[i].ri = tmp.back().ri;
					nw[i].lv = nw[i].rv = 0;
				}
				for (int i = 0; i < tmp.size(); i ++) {
					int l = i + 1, r = tmp.size() - i;
					if (l >= L) nw[l/L-1].rv += tmp[i].rv;
					if (r >= L) nw[c-r/L].lv += tmp[i].lv;
				}
				ans -= calc(nw);
				for (auto q:nw) all.push_back(q);
			}
        }
		for (auto q:all) S.insert(q);
        now ++;
	}
	cout<<ans;
}
