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
// Remember...

#include<bits/stdc++.h>

#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

const int maxn=1e5+10, inf=2e9;

int n,k;

vector< pair<int, pll> >vec;
vector<pll> vec2, vec3;

ll ans;

void handle();

ll solve(vector<pll> &v){
    ll ans=0, sm=0;
    for(auto p:v){
	ans+= p.F * p.S;
	sm+= p.S;
    }
    if(sz(v)<k) return ans;
    
    for(int i=0;i<k-1;i++){
	sm-= v[i].S;
    }
    for(int i=0;i<sz(v)-k+1;i++){
	ans+= v[i].F * sm;
	sm-= v[i+k-1].S;
    }
    return ans;
}
void add(int x){
    while(vec.back().F < x) handle();
    vec.PB({x,{1,1}});
}
void handle(){
    int x=vec.back().F;
    vec2.clear();
    while(vec.back().F == x){
	vec2.PB(vec.back().S);
	vec.pop_back();
    }
    reverse(vec2.begin(),vec2.end());
    ans+= solve(vec2);
    
    if(sz(vec2)<k){ add(inf); return; }
    vec3.resize( sz(vec2)/k );

    for(int i=k;i<=sz(vec2);i+=k){
	ll sm=0;
	for(int j=i;j<=min(sz(vec2),i+k-1);j++)
	    sm+= vec2[j-1].S;
	vec3[(i/k)-1].S= sm;
    }    
    reverse(vec2.begin(),vec2.end());
    reverse(vec3.begin(),vec3.end());
    for(int i=k;i<=sz(vec2);i+=k){
	ll sm=0;
	for(int j=i;j<=min(sz(vec2),i+k-1);j++)
	    sm+= vec2[j-1].F;
	vec3[(i/k)-1].F= sm;
    }
    reverse(vec3.begin(),vec3.end());

    ans-= solve(vec3);

    for(auto p:vec3){
	vec.PB({x+1,p});
    }
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie();

    cin>>n>>k;
    vec.PB({inf,{1,1}});   
    while(n--){
	int x; cin>>x;
	add(x);
    }
    add(inf);    
    return cout<<ans<<endl,0;
}
// Deathly mistakes:
//  * Read the problem carefully.
//  * Check maxn.
//  * Overflows.


// #pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
