#include <bits/stdc++.h>
using namespace std;
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;
}
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;
long long ans;
long long calc(vector<node> &cur) {
  long long sum = 0, all = 0;
  for (int i = 0; i + L - 1 < (int)cur.size(); ++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());
    }
    if (N2.empty())
      ans += calc(mn);
    else
      for (int i = 0, pi = 1; i < (int)mn.size(); i = pi, pi = i + 1) {
        while (pi < (int)mn.size() && ++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 < (int)tmp.size(); ++j)
            ntmp[cnt - ((int)tmp.size() - j) / L].l += tmp[j].l;
          for (int j = L - 1; j < (int)tmp.size(); ++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;
}
