#include <bits/stdc++.h>
using namespace std;
struct Node {int l, r, x;};
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, l;
    cin >> n >> l;
    vector<int> a(n);
    for (int i = 0; i < n; ++i)
        cin >> a[i];
    struct Node {
        int pre, nxt, val, l, r;
        bool isNew;
    };
    vector<Node> t(n);
    vector<pair<int, int>> s;
    for (int i = 0; i < n; ++i) {
        t[i].pre = i - 1;
        t[i].nxt = i == n - 1 ? -1 : i + 1;
        t[i].l = t[i].r = 1;
        t[i].val = a[i];
        t[i].isNew = false;
        s.emplace_back(a[i], i);
    }
    sort(s.begin(), s.end(), greater<pair<int, int>>());
    long long ans = 0;
    auto connect = [&](int l, int r) {
        if (l != -1)
            t[l].nxt = r;
        if (r != -1)
            t[r].pre = l;
    };
    while (!s.empty()) {
        int x = s.back().first;
        vector<int> v, v1;
        while (!s.empty() && s.back().first == x) {
            int p = s.back().second;
            if (t[p].pre == -1 || t[t[p].pre].val != x)
                v.push_back(p);
            if ((t[p].pre == -1 || t[t[p].pre].val != x || !t[t[p].pre].isNew) && t[p].isNew)
                v1.push_back(p);
            s.pop_back();
        }
        for (int p : v1) {
            vector<int> ver;
            for (int i = p; ; i = t[i].nxt) {
                if (i == -1 || t[i].val != x || !t[i].isNew)
                    break;
                ver.push_back(i);
            }
            int sum = 0;
            for (int i = l - 1; i < (int)ver.size(); ++i) {
                sum += t[ver[i - l + 1]].l;
                ans -= 1LL * sum * t[ver[i]].r;
            }
        }
        for (int p : v) {
            vector<int> ver;
            for (int i = p; ; i = t[i].nxt) {
                if (i == -1 || t[i].val != x)
                    break;
                ver.push_back(i);
            }
            if ((int)ver.size() < l) {
                connect(t[p].pre, -1);
                connect(-1, t[ver.back()].nxt);
                continue;
            }
            int sum = 0;
            for (int i = l - 1; i < (int)ver.size(); ++i) {
                sum += t[ver[i - l + 1]].l;
                ans += 1LL * sum * t[ver[i]].r;
            }
            int cnt = ver.size() / l;
            vector<int> newL(cnt), newR(cnt);
            for (int i = l - 1; i < (int)ver.size(); ++i) {
                newL[cnt - (i - l + 1) / l - 1] += t[ver[ver.size() - i - 1]].l;
                newR[(i - l + 1) / l] += t[ver[i]].r;
            }
            int lst = t[p].pre;
            for (int i = 0; i < cnt; ++i) {
                ++t[ver[i]].val;
                t[ver[i]].isNew = true;
                t[ver[i]].l = newL[i];
                t[ver[i]].r = newR[i];
                connect(lst, ver[i]);
                s.emplace_back(t[ver[i]].val, ver[i]);
                lst = ver[i];
            }
            connect(lst, t[ver.back()].nxt);
        }
    }
    cout << ans + n << endl;
    return 0;
}