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=200000;

int n,m,a[N+9];

void into(){
  scanf("%d%d",&n,&m);
  for (int i=1;i<=n;++i)
	scanf("%d",&a[i]);
}

int sta[N+9],cst;
int pre[N+9],suf[N+9],spre[N+9],ssuf[N+9];
LL ans;

void Get_ans0(){
  int now=sta[cst],cnt=0;
  for (;cst&&sta[cst]==now;--cst) ++cnt;
  if (cnt<m){
	for (;cst;) Get_ans0();
	return;
  }
  int c=cnt/m;
  for (int i=1;i<=cnt;++i) spre[i]=spre[i-1]+pre[i+cst],ssuf[i]=ssuf[i-1]+suf[i+cst];
  for (int i=m;i<=cnt;++i) ans+=(LL)spre[i-m+1]*suf[i+cst];
  for (int i=1;i<=c;++i){
	pre[i+cst]=spre[cnt-m*(c-i+1)+1]-spre[max(cnt-m*(c-i+2)+1,0)];
	suf[i+cst]=ssuf[min(m*(i+1)-1,cnt)]-ssuf[m*i-1];
  }
  for (int i=m,s=0;i<=c;++i) ans-=(LL)(s+=pre[cst+i-m+1])*suf[i+cst];
  for (int i=1;i<=c;++i) sta[++cst]=now+1;
}

void Get_ans(){
  for (int i=1;i<=n;++i){
	for (;cst&&sta[cst]<a[i];) Get_ans0();
	sta[++cst]=a[i];
	pre[cst]=suf[cst]=1;
  }
  for (;cst;) Get_ans0();
}

void work(){
  Get_ans();
}

void outo(){
  printf("%lld\n",ans+n);
}

int main(){
  into();
  work();
  outo();
  return 0;
}