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 ff first
#define ss second
#define pb push_back
#define mp make_pair
typedef long long LL;
typedef unsigned long long uLL;
typedef pair<int,int> pii;

const int maxn=200111;
int n,l,a[maxn],f[maxn],lv[maxn],rv[maxn];
LL ans;
int gf(int x){return x==f[x]?x:f[x]=gf(f[x]);}

int main()
{
	scanf("%d%d",&n,&l);
	
	set<pii> st;
	for(int i=1;i<=n;i++)
	{
		scanf("%d",a+i);
		st.insert(mp(a[i],i));
		f[i]=i;lv[i]=rv[i]=1;
	}
	f[n+1]=n+1;
	while(st.size())
	{
		int mn=st.begin()->ff,cur=st.begin()->ss,sum;
		vector<int> vs;
		while(cur<=n&&a[cur]==mn)
		{
			st.erase(mp(mn,cur));
			vs.pb(cur);
			cur=gf(cur+1);
		}
		
		if((int)vs.size()<l)continue;
		cur=0;sum=0;
		for(int i=0;i<(int)vs.size();i++)
		{
			while(cur<(int)vs.size()&&i-cur+1>=l)sum+=lv[vs[cur++]];
			ans+=(LL)sum*rv[vs[i]];
		}
		int sz=(int)vs.size()/l;
		vector<int> nl,nr;
		for(int i=1;i<=sz;i++)
		{
			int lb=i*l-1,rb=min((i+1)*l-1,(int)vs.size()),s=0;
			for(int j=lb;j<rb;j++)s+=rv[vs[j]];
			nr.pb(s);
		}
		reverse(vs.begin(),vs.end());
		for(int i=1;i<=sz;i++)
		{
			int lb=i*l-1,rb=min((i+1)*l-1,(int)vs.size()),s=0;
			for(int j=lb;j<rb;j++)s+=lv[vs[j]];
			nl.pb(s);
		}
		reverse(nl.begin(),nl.end());
		reverse(vs.begin(),vs.end());
		
		for(int i=0;i<sz;i++)
		{
			lv[vs[i]]=nl[i];
			rv[vs[i]]=nr[i];
		}
		for(int i=sz;i<(int)vs.size();i++)f[vs[i]]=vs[i]+1;
		vs.resize(sz);
		
		cur=0;sum=0;
		for(int i=0;i<(int)vs.size();i++)
		{
			while(cur<(int)vs.size()&&i-cur+1>=l)sum+=lv[vs[cur++]];
			ans-=(LL)sum*rv[vs[i]];
		}
		for(int i=0;i<(int)vs.size();i++)
		{
			a[vs[i]]++;
			st.insert(mp(a[vs[i]],vs[i]));
		}
	}
	printf("%lld\n",ans+n);
	return 0;
}