// 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")
