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>
#define last last2

using namespace std;

typedef long long ll;

int num[200005],n,L;
ll ans;

namespace SGT {

int maxv[800000];

void build(int l,int r,int o) {
  if (l==r) maxv[o]=l;
  else {
  	int m=((l+r)>>1);
    build(l,m,o*2);
    build(m+1,r,o*2+1);
    maxv[o]=((num[maxv[o*2]]>=num[maxv[o*2+1]])?maxv[o*2]:maxv[o*2+1]);
  }
}

int query(int l,int r,int o,int lx,int rx) {
  if (l>=lx&&r<=rx) return maxv[o];
  else {
  	int m=((l+r)>>1);
  	if (m>=rx) return query(l,m,o*2,lx,rx);
  	if (m<lx) return query(m+1,r,o*2+1,lx,rx);
  	int a=query(l,m,o*2,lx,rx),b=query(m+1,r,o*2+1,lx,rx);
  	return (num[a]>=num[b])?a:b;
  }
}

}

int nxt[200005],powd[200005];
map <int,int> last;

void pre() {
  powd[0]=1;
  for(int i=1;i<=n;i++) powd[i]=min((ll)powd[i-1]*L,n+1LL);
  for(int i=n;i>0;i--) {
  	nxt[i]=((last[num[i]])?last[num[i]]:n+1);
  	last[num[i]]=i;
  } 
}

vector <int> suml[200005],sumr[200005];
vector <int> pos[200005],son[200005];
int size[200005],lsize[200005],rsize[200005];
int val[200005],tot;

void calc(int o,int d) {
  static int sum[200005];
  if (d>n||powd[d]>n) {
  	size[o]=-1;
  	suml[o].resize(1);sumr[o].resize(1);
  	lsize[o]=rsize[o]=0;
  	return;
  }
  size[o]=((size[o]>=powd[d])?size[o]/powd[d]:-1);
  if (lsize[o]) {
  	for(int i=1;i<=lsize[o];i++) sum[i]=0;
    int maxn=0;
    for(int i=powd[d];i<=lsize[o];i++) {
      maxn=i/powd[d];
	  sum[maxn]+=suml[o][i];
    }
    lsize[o]=maxn;
    suml[o].resize(maxn+1);
    for(int i=1;i<=maxn;i++) suml[o][i]=sum[i];
  }
  if (rsize[o]) {
  	for(int i=1;i<=rsize[o];i++) sum[i]=0;
    int maxn=0;
    for(int i=powd[d];i<=rsize[o];i++) {
      maxn=i/powd[d];
	  sum[maxn]+=sumr[o][i];
    }
    rsize[o]=maxn;
    sumr[o].resize(maxn+1);
    for(int i=1;i<=maxn;i++) sumr[o][i]=sum[i];
  }
}

int solve(int l,int r) {
  static int q[200005];
  int o=++tot;
  for(int i=SGT::query(1,n,1,l,r);i<=r;i=nxt[i]) 
    pos[o].push_back(i);
  val[o]=num[pos[o][0]];
  son[o].resize(pos[o].size()+1);
  if (pos[o][0]>l) son[o][0]=solve(l,pos[o][0]-1);
  for(int i=1;i<pos[o].size();i++)
    if (pos[o][i]>pos[o][i-1]+1) son[o][i]=solve(pos[o][i-1]+1,pos[o][i]-1);
  if (pos[o][pos[o].size()-1]<r) son[o][son[o].size()-1]=solve(pos[o][pos[o].size()-1]+1,r);
  for(int i=0;i<son[o].size();i++)
    if (son[o][i]) calc(son[o][i],val[o]-val[son[o][i]]);
  int rx=0,lx=0;
  for(int i=rsize[son[o][0]];i>0;i--) q[++rx]=sumr[son[o][0]][i];
  int s=0;
  for(int i=0;i<pos[o].size();i++) {
  	q[++rx]=1;
  	while (lx<rx&&rx-lx>=L) s+=q[++lx];
  	ans+=s;
  	if (son[o][i+1]) {
  		int u=son[o][i+1];
  		for(int j=1;j<=lsize[u];j++) {
  			while (lx<rx&&rx-lx+j>=L) s+=q[++lx];
  			ans+=(ll)s*suml[u][j];
		  }
		if (size[u]==-1) lx=rx,s=0;
		for(int j=rsize[u];j>0;j--) q[++rx]=sumr[u][j];
	  }
  }
  bool v=1;
  int sz=pos[o].size();
  for(int i=0;i<son[o].size();i++)
    if (size[son[o][i]]==-1) v=0; else sz+=size[son[o][i]];
  size[o]=((v)?sz:-1);
  suml[o].resize(1);
  for(int i=0;i<son[o].size();i++) {
  	int u=son[o][i];
  	for(int j=1;j<=lsize[u];j++) suml[o].push_back(suml[u][j]);
  	if (size[u]==-1) break;
  	if (i+1<son[o].size()) suml[o].push_back(1);
  }
  lsize[o]=suml[o].size()-1;
  sumr[o].resize(1);
  for(int i=son[o].size()-1;i>=0;i--) {
  	int u=son[o][i];
  	for(int j=1;j<=rsize[u];j++) sumr[o].push_back(sumr[u][j]);
  	if (size[u]==-1) break;
  	if (i) sumr[o].push_back(1);
  }
  rsize[o]=sumr[o].size()-1;
  return o;
}

int main() {
  scanf("%d%d",&n,&L);
  for(int i=1;i<=n;i++) scanf("%d",&num[i]);
  pre();
  SGT::build(1,n,1);
  solve(1,n);
  printf("%lld\n",ans+n);
  return 0;
}