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 <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <cstring>
#define SIZE 200005

using namespace std;
typedef long long int ll;
typedef pair <int,int> P;
typedef pair <P,P> PP;

int A[SIZE];

ll solve(vector <P> vec,int L)
{
	int n=vec.size();
	ll ret=0,sum=0;
	for(int i=L-1;i<n;i++)
	{
		sum+=vec[i-L+1].first;
		ret+=sum*vec[i].second;
	}
	return ret;
}
int main()
{
	int n,L;
	scanf("%d %d",&n,&L);
	for(int i=0;i<n;i++) scanf("%d",&A[i]);
	if(L==1)
	{
		printf("%lld\n",(ll) n*(ll) (n+1)/2);
		return 0;
	}
	vector <P> all;
	for(int i=0;i<n;i++) all.push_back(P(A[i],i));
	sort(all.begin(),all.end());
	int now=-1,pos=0;
	vector <PP> vec;
	ll ret=n;
	while(1)
	{
		if(vec.empty())
		{
			if(pos==all.size()) break;
			now=all[pos].first;
		}
		while(pos<all.size()&&all[pos].first==now)
		{
			int v=all[pos++].second;
			vec.push_back(PP(P(v,v),P(1,1)));
		}
		sort(vec.begin(),vec.end());
		//printf("%d : ",now);
		//for(int i=0;i<vec.size();i++) printf("[%d %d : %d %d] ",vec[i].first.first,vec[i].first.second,vec[i].second.first,vec[i].second.second);puts("");
		vector <PP> nxt;
		for(int i=0;i<vec.size();)
		{
			int f=i++;
			for(;i<vec.size()&&vec[i].first.first==vec[i-1].first.second+1;i++);
			vector <P> now;
			for(int j=f;j<i;j++) now.push_back(vec[j].second);
			if(now.size()>=L)
			{
				ret+=solve(now,L);
				int c=now.size()/L;
				vector <P> v1,v2;
				for(int j=0;j<c;j++)
				{
					int s=vec[f].first.first+j,t=s;
					if(j==c-1) t=vec[i-1].first.second;
					v1.push_back(P(s,t));
					v2.push_back(P(0,0));
				}
				for(int j=f;j<i;j++)
				{
					int l=j-f+1,r=i-j;
					if(l>=L)
					{
						v2[l/L-1].second+=vec[j].second.second;
					}
					if(r>=L)
					{
						v2[c-r/L].first+=vec[j].second.first;
					}
				}
				ret-=solve(v2,L);
				for(int j=0;j<c;j++) nxt.push_back(PP(v1[j],v2[j]));
			}
		}
		vec=nxt;
		now++;
	}
	printf("%lld\n",ret);
	return 0;
}
