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
#define ui unsigned int
#define ull unsigned long long
#define db long double
#define pii pair<int,int>
#define pli pair<ll,int>
#define X first
#define Y second
#define mp make_pair
#define pb push_back
#define vi vector<int>
#define vii vector<vi>
#define lb lower_bound
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,b,a) for(int i=(b);i>=(a);--i)
#define rep0(i,a,b) for(int i=(a);i<(b);++i)
#define fore(i,a) for(int i=0;i<a.size();++i)
#define gc() getchar()
#define ls x<<1,l,m
#define rs x<<1|1,m+1,r
inline ll rd()
{
	ll x=0,w=1;char c=gc();while(!isdigit(c)&&c!='-')c=gc();
	if(c=='-')c=gc(),w=-1;while(isdigit(c))x=x*10+c-48,c=gc();return x*w;
}
const int N=200005;
int n,L,pre[N],nxt[N];ll ans,f1[N],f2[N],g1[N],g2[N];
vi V1,V2;priority_queue<pii,vector<pii>,greater<pii> >Q;
inline void link(int x,int y){pre[y]=x;nxt[x]=y;}
inline ll calc(int x)
{
	int m=V2.size(),c=m/L,pl=pre[V2[0]],pr=nxt[V2[m-1]];ll res=0;
	ll s=0;rep0(i,0,m){s+=i>=L-1?f1[V2[i-L+1]]:0;res+=s*f2[V2[i]];}
	for(int i:V2)g1[i]=f1[i],g2[i]=f2[i],f1[i]=f2[i]=0;
	if(!c){nxt[pl]=n+1,pre[pr]=0;return res;}
	rep0(i,L-1,m){int t=(i+1)/L-1;f2[V2[t]]+=g2[V2[i]];}
	per(i,m-L,0){int t=c-(m-i)/L;f1[V2[t]]+=g1[V2[i]];}
	link(pl,V2[0]);rep0(i,1,c)link(V2[i-1],V2[i]);link(V2[c-1],pr);
	rep0(i,0,c)Q.push(mp(x+1,V2[i]));
	s=0;rep0(i,0,c){s+=i>=L-1?f1[V2[i-L+1]]:0;res-=s*f2[V2[i]];}
	return res;
}
int main()
{
	n=rd();L=rd();rep(i,0,n)link(i,i+1);
	rep(i,1,n){Q.push(mp(rd(),i));f1[i]=f2[i]=1;}
	while(!Q.empty())
	{
		int x=Q.top().X;V1.clear();V2.clear();
		while(!Q.empty()&&Q.top().X==x)V1.pb(Q.top().Y),Q.pop();
		fore(i,V1)
		{
			if(i&&nxt[V1[i-1]]!=V1[i])ans+=calc(x),V2.clear();
			V2.pb(V1[i]);
		}
		ans+=calc(x);
	}
	printf("%lld\n",ans+n);return 0;
}
