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 llong long long
#define mkpr make_pair
#define pii pair<int,int>
#define riterator reverse_iterator
using namespace std;

inline int read()
{
	int x = 0,f = 1; char ch = getchar();
	for(;!isdigit(ch);ch=getchar()) {if(ch=='-') f = -1;}
	for(; isdigit(ch);ch=getchar()) {x = x*10+ch-48;}
	return x*f;
}

const int N = 2e5;
priority_queue<pii,vector<pii>,greater<pii> > que;
int nxt[N+3],prv[N+3];
int a[N+3];
llong cl[N+3],cr[N+3],cl2[N+3],cr2[N+3];
vector<int> vec;
int n,m; llong ans;

void solve(int l,int r)
{
//	printf("solve %d %d\n",l,r);
	llong sum = 0ll;
	for(int i=m-1; i<vec.size(); i++)
	{
		sum += cl[vec[i-m+1]];
		ans += cr[vec[i]]*sum;
	}
	int cnt = vec.size()/m;
	for(int i=l; i<=l+cnt-1; i++) cl2[i] = cr2[i] = 0ll;
	for(int i=vec.size()-m,j=0,k=l+cnt-1; i>=0; i--)
	{
		cl2[k] += cl[vec[i]];
		if(j==m-1) {k--,j=0;}
		else {j++;}
	}
	for(int i=m-1,j=0,k=l; i<vec.size(); i++)
	{
		cr2[k] += cr[vec[i]];
		if(j==m-1) {k++,j=0;}
		else {j++;}
	}
	for(int i=l; i<=l+cnt-1; i++) cl[i] = cl2[i],cr[i] = cr2[i];
	sum = 0ll;
	for(int i=l+m-1; i<=l+cnt-1; i++)
	{
		sum += cl[i-m+1];
		ans -= cr[i]*sum;
	}
	if(cnt==0)
	{
		nxt[prv[l]] = n+1; prv[nxt[r]] = 0;
	}
	else
	{
		nxt[l+cnt-1] = nxt[r]; prv[nxt[r]] = l+cnt-1;
		for(int i=l; i<l+cnt-1; i++) nxt[i] = i+1;
		for(int i=l+1; i<=l+cnt-1; i++) prv[i] = i-1;
		int val = a[l]; for(int i=l; i<=l+cnt-1; i++) a[i] = val+1;
		for(int i=l; i<=l+cnt-1; i++) que.push(mkpr(a[i],i));
	}
//	printf("cnt=%d\n",cnt);
//	printf("prv: "); for(int i=1; i<=n+1; i++) printf("[%d]%d ",i,prv[i]); puts("");
//	printf("nxt: "); for(int i=0; i<=n; i++) printf("[%d]%d ",i,nxt[i]); puts("");
//	printf("cl: "); for(int i=1; i<=n; i++) printf("[%d]%lld ",i,cl[i]); puts("");
//	printf("cr: "); for(int i=1; i<=n; i++) printf("[%d]%lld ",i,cr[i]); puts("");
}

int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1; i<=n; i++) scanf("%d",&a[i]),que.push(mkpr(a[i],i)),cl[i] = cr[i] = 1ll,nxt[i] = i+1,prv[i] = i-1;
	nxt[0] = 1,prv[n+1] = n;
	while(1)
	{
		int l = que.top().second,r = l; que.pop(); vec.clear(); vec.push_back(l);
		while(!que.empty() && que.top().first==a[l] && que.top().second==nxt[r]) {r = nxt[r]; vec.push_back(r); que.pop();}
		solve(l,r);
		if(que.empty()) break;
	}
	printf("%lld\n",ans+n);
	return 0;
}
/*
4 3
4 3 4 4
*/