#include <bits/stdc++.h>
#define ll long long
#define db long double
#define x first
#define y second
#define mp make_pair
#define pb push_back
#define all(a) a.begin(), a.end()

using namespace std;

struct Vertex{int l; int r; int pr; int sz; int value; ll suf; ll pref; int minimum;};
vector<Vertex> decart;
pair<int, int> SP = make_pair(-1, -1);
int create_vertex(int value, ll pref, ll suf){
	decart.push_back({-1, -1, rand()%1000000000, 1, value, suf, pref, value});
	return decart.size() - 1;
}
void update(int vertex){
    if (vertex == -1) return;
    int sz = 1, minimum = decart[vertex].value;
    if (decart[vertex].l != -1){
        sz += decart[decart[vertex].l].sz;
        minimum = min(minimum, decart[decart[vertex].l].minimum);
    }
    if (decart[vertex].r != -1){
        sz += decart[decart[vertex].r].sz;
        minimum = min(minimum, decart[decart[vertex].r].minimum);
    }
    decart[vertex].sz = sz;
    decart[vertex].minimum = minimum;
}
pair<int, int> split(int father, int number){
    if (father == -1) return SP;
    int l = 1;
    if (decart[father].l != -1){
        l += decart[decart[father].l].sz;
    }
    if (l <= number){
        pair<int, int> p = split(decart[father].r, number - l);
        decart[father].r = p.first;
        p.first = father;
        update(father);
        return p;
    }
    pair<int, int> p = split(decart[father].l, number);
    decart[father].l = p.second;
    p.second = father;
    update(father);
    return p;
}
int merg(int first, int second){
    if (first == -1) return second;
    if (second == -1) return first;
    if (decart[first].pr >= decart[second].pr){
        int v = merg(decart[first].r, second);
        decart[first].r = v;
        update(first);
        return first;
    }
    int v = merg(first, decart[second].l);
    decart[second].l = v;
    update(second);
    return second;
}

int n, l;

ll ans = 0;

const int INF = 2e9;

int get_minimum(int base){
	int L = decart[base].l, R = decart[base].r;
	int a, b, c;
	if (L==-1) a = INF;
	else a = decart[L].minimum;
	b = decart[base].value;
	if (R==-1)c=INF;
	else c = decart[R].minimum;
	int sz = 0;
	if (L!=-1) sz = decart[L].sz;
	if (a <= b && a <= c) return get_minimum(L);
	if (b <= c) return sz;
	return get_minimum(R)+sz+1;
}

int get_left(int base){
	if (base==-1) return -1;
	if (decart[base].l == -1) return decart[base].value;
	return get_left(decart[base].l);
}

vector<pair<ll, ll> > values;
vector<pair<ll, ll> > new_values;

void dfs(int base){
	if (base==-1) return;
	dfs(decart[base].l);
	values.push_back({decart[base].pref, decart[base].suf});
	dfs(decart[base].r);
}

void add(vector<pair<ll, ll> > values, ll kf){
	ll sum = 0;
	for (int i=values.size() - 1; i >= 0; i--){
		int index = i+l-1;
		if (index < values.size()) sum += values[index].first;
		ans += kf*sum*values[i].second;
	}
}

void solve(int base){
	if (base == -1) return;
	int less = get_minimum(base);
	pair<int, int> T = split(base, less);
	int left = T.first, middle = -1, right = T.second;
	int mx = decart[right].minimum;
	while (true){
		int val = get_left(right);
		if (val == mx){
			pair<int, int> Q = split(right, 1);
			right = Q.second;
			middle = merg(middle, Q.first);
		}
		else break;
	}
	if (decart[middle].sz < l){
		solve(left);
		solve(right);
		return;
	}
	values.clear();
	dfs(middle);
	add(values, 1);
	//cout << ans << endl;
	int S = values.size();
	new_values.assign(S/l, {0, 0});
	int F = new_values.size();
	for (int i=values.size()-1; i >= 0; i--){
		int index = (values.size() - i)/l;
		if (index != 0) new_values[F-(index-1) - 1].second += values[i].second;
		index = (i+1)/l;
		if (index != 0) new_values[index-1].first += values[i].first;
	} 
	add(new_values, -1);
	int B = -1;
	for (int i=0;i<new_values.size(); ++i){
		int I = create_vertex(mx+1, new_values[i].first, new_values[i].second);
		B = merg(B, I);
	}
	B = merg(left, B);
	B = merg(B, right);
	solve(B);
}

int main(){
#ifdef LOCAL
	freopen("H_input.txt", "r", stdin);
	//freopen("A_output.txt", "w", stdout);
#endif
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> l;
	vector<int> v(n);
	for (int i=0;i<n;++i) cin >> v[i];
	int base = -1;
	for (int i=0;i<n;++i){
		int I = create_vertex(v[i], 1, 1);
		base = merg(base, I);
	}
	solve(base);
	cout << ans+n;

}


Measured memory_bytes: 36328