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;
typedef long long ll;
const int N=4e5+10;
struct node{int x,L,R,l,r;};
bool operator < (node a,node b){
	if (a.x==b.x)return a.l<b.l;
	return a.x<b.x;
}
set<node> s,s1;
vector<node> d;
int n,L;
ll ans;
int al[N],ar[N],q[N],pl[N],pr[N];
void calc(int x){
	ll cnt=0;
	for (int i=0;i<d.size();i++){
		if (i>=L-1)cnt+=d[i-L+1].L;
		ans+=cnt*d[i].R;
	}
	int c1=1,t=0,t1,L1=0;
	L1=d[0].l;
	for (int i=0;i<d.size();i++){
		if (c1==L){
			ar[++t]=0;
			pl[t]=1e9;
			pr[t]=0;
			c1=0;
		}
		ar[t]+=d[i].R;
		pl[t]=min(pl[t],d[i].l);
		pr[t]=max(pr[t],d[i].r);
		c1++;
	}t1=t;
	c1=1,t++;
	for (int i=d.size()-1;i>=0;i--){
		if (c1==L){
			al[--t]=0;
//			pl[t]=1e9;
//			pr[t]=0;
			c1=0;
		}
		al[t]+=d[i].L;
		c1++;
	}
	d.clear();
	pl[1]=L1;
	for (int i=1;i<=t1;i++){
		d.push_back((node){x+1,al[i],ar[i],pl[i],pr[i]});
	}
	cnt=0;
	for (int i=0;i<d.size();i++){
		if (i>=L-1)cnt+=d[i-L+1].L;
		ans-=cnt*d[i].R;
	}
}
int main(){
	cin>>n>>L;
	for (int i=1;i<=n;i++){
		int x;
		scanf("%d",&x);
		s.insert((node){x,1,1,i,i});
	}
	while (s.size()){
		s1.clear();
		int v=s.begin()->x;
		for (auto i:s){
			if (!d.empty()){
				if (d.back().r+1<i.l||i.x!=v){
					for (auto x:d)s.erase(x);
					if (d.size()<L){
						d.clear();
					}
					else calc(v);
					for (auto x:d)s.insert(x);
					d.clear();
					break;
				}
			}
			if (i.x!=v)break;
			d.push_back(i);
		}
		int tag=0;
		while (d.size()>=L){
			calc(v);
			tag=1;
		}
		if (d.size()||tag)break;
	}
	cout<<ans+n<<endl;
}