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<queue>
using namespace std;
const int N=200005;
int n,l;
int a[N];
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >q;
int pre[N],nxt[N];
long long lf[N],rf[N];
vector<int>now;
long long solve(int x)
{
	long long res=0,sum=0;
	int len=now.size();
	int ppre=pre[now.front()],nnxt=nxt[now.back()];
	for(int i=0;i<len;i++)
	{
		if(i-l+1>=0) sum+=lf[now[i-l+1]];
		res+=sum*rf[now[i]];
	}
	static long long tlf[N],trf[N];
	for(int i=0;i<len;i++)
		tlf[now[i]]=lf[now[i]],trf[now[i]]=rf[now[i]],lf[now[i]]=rf[now[i]]=0;
	if(len<l)
	{
		nxt[ppre]=n+1,pre[nnxt]=0;
		return res;
	}
	int num=len/l;
	for(int i=l-1;i<len;i++)
	{
		int p=(i+1)/l-1;
		rf[now[p]]+=trf[now[i]];
	}
	for(int i=len-l;i>=0;i--)
	{
		int p=num-(len-i)/l;
		lf[now[p]]+=tlf[now[i]];
	}
	now.resize(num);
	for(int i=1;i<num;i++)
		pre[now[i]]=now[i-1],nxt[now[i-1]]=now[i];
	pre[now.front()]=ppre,nxt[ppre]=now.front();
	pre[nnxt]=now.back(),nxt[now.back()]=nnxt;
	for(int p:now)
		q.push(make_pair(x+1,p));
	sum=0;
	for(int i=0;i<num;i++)
	{
		if(i-l+1>=0) sum+=lf[now[i-l+1]];
		res-=sum*rf[now[i]];
	}
	return res;
}
int main()
{
	scanf("%d%d",&n,&l);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	for(int i=1;i<=n;i++)
	{
		q.push(make_pair(a[i],i));
		pre[i]=i-1,nxt[i]=i+1;
		lf[i]=rf[i]=1;
	}
	vector<int>pos;
	long long ans=0;
	while(!q.empty())
	{
		int x=q.top().first;
		pos.push_back(q.top().second);
		q.pop();
		while(!q.empty()&&q.top().first==x) pos.push_back(q.top().second),q.pop();
		now.push_back(pos.front());
		for(int i=1;i<pos.size();i++)
		{
			if(nxt[pos[i-1]]!=pos[i]) ans+=solve(x),now.clear();
			now.push_back(pos[i]);
		}
		ans+=solve(x);
		now.clear();
		pos.clear();
	}
	printf("%lld",ans+n);
	return 0;
}