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 <algorithm>
#include <cassert>
#include <cstdio>
#include <iostream>
#include <vector>
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define fi first
#define se second
using namespace std;
inline char nc()
{
	return getchar();
	static char buf[100000],*l=buf,*r=buf;
	return l==r&&(r=(l=buf)+fread(buf,1,100000,stdin),l==r)?EOF:*l++; 
}
template<class T> void read(T &x)
{
	x=0; int f=1,ch=nc();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=nc();}
	while(ch>='0'&&ch<='9'){x=x*10-'0'+ch;ch=nc();}
	x*=f;
}
typedef long long ll;
typedef pair<int,int> pii; 
const int maxn=2e5+50;
const int maxp=maxn*25;
int n,L;
vector<pii> num;
struct node
{
	int l,r,L,R;
	node(int l=0,int r=0,int L=0,int R=0):l(l),r(r),L(L),R(R){}
	inline bool operator <(const node &other) const
	{
		return l<other.l;
	}
};
vector<node> rec[2];
int main()
{
//	freopen("1.in","r",stdin);
//	freopen("1.out","w",stdout); 
	read(n), read(L);
	for(int i=1;i<=n;++i)
	{
		int x; read(x);
		num.push_back(make_pair(x,i));
	}
	sort(num.begin(),num.end());
	ll an=n;
	int cur=0,now=0,pt=0;
	while(true)
	{
		cur^=1; rec[cur^1].clear();
		if(rec[cur].size()==0)
		{
			if(pt<num.size()) now=num[pt].fi;
			else break;
		}
		else ++now;
		while(pt<num.size()&&num[pt].fi==now) rec[cur].push_back(node(num[pt].se,num[pt].se,1,1)),++pt;
		sort(rec[cur].begin(),rec[cur].end());
		for(int l=0,r;l<rec[cur].size();l=r+1)
		{
			static node tmp[maxn]; 
			r=l; while(r+1<rec[cur].size()&&rec[cur][r+1].l==rec[cur][r].r+1) ++r;
			if(r-l+1<L) continue;
			for(int j=r,sum=0;j>=l+L-1;--j) 
			{
				sum+=rec[cur][j].R;
				an+=(ll)rec[cur][j-L+1].L*sum;
			}
			int k=(r-l+1)/L; tmp[0].l=rec[cur][l].l-1;
			for(int j=1;j<=k;++j)
			{
				tmp[j].l=tmp[j].r=tmp[j-1].l+1;
				tmp[j].L=tmp[j].R=0;
			}
			tmp[k].r=rec[cur][r].r;
			for(int j=l;j<=r;++j)
			{
				int x=j-l+1,y=r-j+1;
				if(x>=L) tmp[x/L].R+=rec[cur][j].R;
				if(y>=L) tmp[k-y/L+1].L+=rec[cur][j].L;
			}
			for(int j=k,sum=0;j>=L;--j)
			{
				sum+=tmp[j].R;
				an-=(ll)tmp[j-L+1].L*sum;
			}
			for(int j=1;j<=k;++j) rec[cur^1].push_back(tmp[j]);
		}
	}
	printf("%lld\n",an);
	return 0;
}