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 sz(x) (int)x.size()

int read(){
	int a = 0; char c = getchar(); bool f = 0;
	while(!isdigit(c)){f = c == '-'; c = getchar();}
	while(isdigit(c)){
		a = a * 10 + c - 48; c = getchar();
	}
	return f ? -a : a;
}

#define ll long long
struct node{int plc , val , l , r;};
struct cmp1{bool operator ()(node a , node b){return a.plc < b.plc;}};
struct cmp2{bool operator ()(node a , node b){return a.val < b.val || a.val == b.val && a.plc < b.plc;}};
set < node , cmp1 > N1; set < node , cmp2 > N2;
int N , L; ll ans;

ll calc(vector < node > &cur){
	ll sum = 0 , all = 0;
	for(int i = 0 ; i + L - 1 < sz(cur) ; ++i){
		sum += cur[i].l;
		all += sum * cur[i + L - 1].r;
	}
	return all;
}

int main(){
	N = read(); L = read();
	for(int i = 1 ; i <= N ; ++i){
		node now; now.plc = i; now.val = read(); now.l = now.r = 1;
		N1.insert(now); N2.insert(now);
	}
	while(!N2.empty()){
		int val = N2.begin()->val; vector < node > mn;
		while(N2.begin()->val == val){mn.push_back(*N2.begin()); N2.erase(*N2.begin());}
		for(int i = 0 , pi = 1 ; i < sz(mn) ; i = pi , pi = i + 1){
			while(pi < sz(mn) && ++N1.find(mn[pi - 1]) == N1.find(mn[pi])) ++pi;
			vector < node > tmp; tmp.insert(tmp.end() , mn.begin() + i , mn.begin() + pi);
			int len = pi - i , cnt = len / L;
			if(cnt){
				ans += calc(tmp); vector < node > ntmp;
				for(auto t : tmp) N1.erase(t);
				for(int j = 0 ; j < cnt ; ++j) ntmp.push_back((node){tmp[0].plc + j , val + 1 , 0 , 0});
				for(int j = 0 ; j + L - 1 < sz(tmp) ; ++j) ntmp[cnt - (sz(tmp) - j) / L].l += tmp[j].l;
				for(int j = L - 1 ; j < sz(tmp) ; ++j) ntmp[(j + 1) / L - 1].r += tmp[j].r;
				ans -= calc(ntmp);
				for(auto t : ntmp){N1.insert(t); N2.insert(t);}
			}
		}
	}
	cout << ans + N;
	return 0;
}
