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 ll long long

struct node
{
	int l,r,from,L,R;
	node() {}
	node(int l1,int r1,int from1,int L1,int R1):l(l1),r(r1),from(from1),L(L1),R(R1) {}
}g[200010];

inline bool operator <(const node &x,const node &y) { return x.l<y.l; }

set<node> st;
vector<int> v[200010];

int L[200010],R[200010];
int num[200010],h[200010],n,m,l,tt,tot;

inline int rd()
{
	int x=0;char ch=getchar();
	for (;ch<'0'||ch>'9';ch=getchar());
	for (;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
	return x;
}

inline ll calc(int j,int k)
{
	static ll suf[200010];
	ll res=0;int now=j;
	suf[k+1]=0;
	for (int i=k;i>=j;i--) suf[i]=suf[i+1]+g[i].R;
	for (int i=j;i<=k;i++)
	{
		while (now<=k&&(g[now].from==g[i].from||now-i+1<l)) now++;
		if (now<=k) res+=(ll)g[i].L*suf[now];
		else break;
	}
	return res;
}

int main()
{
	n=rd();l=rd();
	for (int i=1;i<=n;i++) num[i]=rd();
	tt=0;
	for (int i=1;i<=n;i++) h[++tt]=num[i];
	sort(h+1,h+tt+1);
	tt=unique(h+1,h+tt+1)-h-1;
	for (int i=1;i<=n;i++) v[lower_bound(h+1,h+tt+1,num[i])-h].push_back(i);
	tot=0;
	ll ans=n;h[tt+1]=INT_MAX;
	for (int i=1;i<=tt;i++)
	{
		for (int t:v[i]) st.insert(node(t,t,++tot,1,1));
		for (int hhh=h[i];hhh<h[i+1]&&!st.empty();hhh++)
		{
			m=0;
			for (set<node>::iterator it=st.begin();it!=st.end();it++) g[++m]=*it;
			st.clear();
			for (int j=1,k;j<=m;j=k+1)
			{
				for (k=j;k<m&&g[k+1].l==g[k].r+1;k++);
				if (k-j+1<l) continue;
				ans+=calc(j,k);
				int hh=(k-j+1)/l;
				for (int i=1;i<=hh;i++) L[i]=R[i]=0;
				for (int i=j;i<=k;i++)
				{
					int h1=(i-j+1)/l,h2=(k-i+1)/l;
					if (h1>0) R[h1]+=g[i].R;
					if (h2>0) L[hh-h2+1]+=g[i].L;
				}
				tot++;
				for (int i=1;i<hh;i++) st.insert(node(g[j].l+i-1,g[j].l+i-1,tot,L[i],R[i]));
				st.insert(node(g[j].l+hh-1,g[k].r,tot,L[hh],R[hh]));
			}
		}
	}
	printf("%lld\n",ans);
	return 0;
}