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 <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <queue>
#include <bitset>
using namespace std;

#ifdef LOCAL
	#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
	#define eprintf(...) 42
#endif

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll;
typedef long double ld;
#define mp make_pair
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int LOG = 18;
const int NN = 200200;
pii sparse[LOG][NN];
int p2[NN];
int n;
ll ans = 0;

pii getMax(int l, int r) {
	int k = p2[r - l];
	return max(sparse[k][l], sparse[k][r - (1 << k)]);
}

int L;

struct Item {
	int K;
	vector<int> toL, toR;
	bool full;

	Item() : K(0), toL(), toR(), full(false) {}

	Item toUpper() {
		Item I = Item();
		I.K = K + 1;
		I.full = full;
		for (int i = 0; i < (int)toL.size(); i++) {
			if ((i + 1) % L == 0)
				I.toL.push_back(0);
			if (!I.toL.empty())
				I.toL.back() += toL[i];
		}
		for (int i = 0; i < (int)toR.size(); i++) {
			if ((i + 1) % L == 0)
				I.toR.push_back(0);
			if (!I.toR.empty())
				I.toR.back() += toR[i];
		}
		if (I.toL.empty() || I.toR.empty()) I.full = false;
		return I;
	}

	void eprint() {
		return;
		eprintf("Item\n");
		eprintf("K = %d\n", K);
		for (int x : toL)
			eprintf("%d ", x);
		eprintf("\n");
		for (int x : toR)
			eprintf("%d ", x);
		eprintf("\n");
		eprintf("full = %d\n", (int)full);
		eprintf("--------\n");
	}
};
struct Fenv {
	int n;
	vector<ll> fenv;

	Fenv() : n(), fenv() {}
	Fenv(int _n) {
		n = _n;
		fenv = vector<ll>(n, 0);
	}

	void add(int p, ll x) {
		for(; p < n; p |= p + 1)
			fenv[p] += x;
	}
	ll get(int r) {
		ll res = 0;
		for(; r >= 0; r = (r & (r + 1)) - 1)
			res += fenv[r];
		return res;
	}
	ll getSum(int l, int r) {
		return get(r - 1) - get(l - 1);
	}

	void clear() {
		for (int i = 0; i < n; i++)
			fenv[i] = 0;
	}
};

Item solve(int l, int r) {
	eprintf("solve %d %d\n", l, r);
	int m = getMax(l, r).first;
	vector<Item> items;
	while(l < r) {
		pii t = getMax(l, r);
		if (t.first != m) {
			Item I = solve(l, r);
			while(I.K < m && (!I.toL.empty() || !I.toR.empty()))
				I = I.toUpper();
			if (I.K != m) I.K = m;
			items.push_back(I);
			break;
		}
		if (t.second + 1 != r) {
			Item I = solve(t.second + 1, r);
			eprintf("HERE 1\n");
			while(I.K < m && (!I.toL.empty() || !I.toR.empty()))
				I = I.toUpper();
			eprintf("HERE 2\n");
			if (I.K != m) I.K = m;
			items.push_back(I);	
		}
		Item I = Item();
		I.K = m;
		I.toL.push_back(1);
		I.toR.push_back(1);
		I.full = true;
		items.push_back(I);
		r = t.second;
	}
	reverse(items.begin(), items.end());
	for (Item I : items)
		I.eprint();
	int tot = 0;
	for (Item I : items)
		tot += max((int)I.toL.size(), (int)I.toR.size());
	Fenv F = Fenv(tot + 2);
	tot = 0;
	for (Item I : items) {
		for (int i = 0; i < (int)I.toL.size(); i++) {
			ans += F.getSum(0, tot + i + 2 - L) * I.toL[i];
		}
		if (!I.full) {
			tot = 0;
			F.clear(); // slow
		}
		tot += (int)I.toR.size();
		for (int i = 0; i < (int)I.toR.size(); i++) {
			F.add(tot - i - 1, I.toR[i]);
		}
	}
	eprintf("ans = %lld\n", ans);
	Item N = Item();
	N.K = m;
	N.full = true;
	for (Item I : items) {
		for (int x : I.toL)
			N.toL.push_back(x);
		if (!I.full) {
			N.full = false;
			break;
		}
	}
	reverse(items.begin(), items.end());
	for (Item I : items) {
		for (int x : I.toR)
			N.toR.push_back(x);
		if (!I.full) {
			N.full = false;
			break;
		}
	}
	eprintf("at the end\n");
	return N;
}

int main()
{
//	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);

	for (int i = 2; i < NN; i++)
		p2[i] = p2[i / 2] + 1;

	scanf("%d%d", &n, &L);
	for (int i = 0; i < n; i++) {
		scanf("%d", &sparse[0][i].first);
		sparse[0][i].second = i;
	}
	for (int k = 0; k < LOG - 1; k++)
		for (int i = 0; i + (1 << (k + 1)) <= n; i++)
			sparse[k + 1][i] = max(sparse[k][i], sparse[k][i + (1 << k)]);
	ans = n;
	solve(0, n);
	printf("%lld\n", ans);

	return 0;
}
