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<iostream>
#include<cstring>
#include<cstdio>
#include<set>
#include<vector>
#include<algorithm>
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,L;
#define Maxn 200010
ll Ans=0;
struct data{
    int val,pos;
    bool operator <(const data &z)const{return val==z.val?pos<z.pos:val<z.val;}
}seq[Maxn];
struct Data{
    int l,r;
	int x,y;
	bool operator <(const Data &z)const{return l<z.l;}
};
vector<Data> A,B,vec2;
vector<pair<int,int> > vec1;
int num[Maxn];

inline ll calc(vector< pair<int,int> > &a){
	ll res=0,sum=0;
	for(int i=L-1,j=0;i<a.size();i++,j++){
		sum+=a[j].first;
		res+=a[i].second*sum;
	}
	return res;
}

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

int main(){
	rd(n);rd(L);
	for(register int i=1;i<=n;++i){
		rd(num[i]);
		seq[i]=(data){num[i],i};
	}
	sort(seq+1,seq+n+1);
	ll Ans=n;
	int at=1,tmp;
	while(true){
		if(A.empty()){
			if(at>n)break;
			else tmp=seq[at].val;
		}else tmp++;
		while(tmp==seq[at].val)A.push_back((Data){seq[at].pos,seq[at].pos,1,1}),at++;
		B.clear();sort(A.begin(),A.end());
		for(int i=0,j;i<A.size();i=j+1){
			j=i;
			while(j+1<A.size()&&A[j+1].l==A[j].r+1)j++;
			int len=j-i+1,cnt=len/L;
			if(cnt){
				vec1.clear();
				vec2.clear();
				for(register int k=i;k<=j;++k)vec1.push_back(make_pair(A[k].x,A[k].y));
				Ans+=calc(vec1);
				for(register int k=1;k<=cnt;++k)
					vec2.push_back((Data){A[i].l+k-1,(k==cnt)?A[j].r:A[i].l+k-1,0,0});
				for(register int k=i;k<=j;++k){
					int tl=k-i+1,tr=j-k+1;
					if(tl>=L)vec2[tl/L-1].y+=A[k].y;
					if(tr>=L)vec2[cnt-tr/L].x+=A[k].x;
				}
				vec1.clear();
			    for(register int k=0;k<cnt;++k)vec1.push_back(make_pair(vec2[k].x,vec2[k].y));
				Ans-=calc(vec1);
				for(register int k=0;k<cnt;++k)B.push_back(vec2[k]);
			}
		}
		A.clear();
		for(int i=0;i<B.size();++i)A.push_back(B[i]);
	}
	printf("%lld\n",Ans);
	return 0;
}