#include <bits/stdc++.h>
int read() {
  int ans = 0, c, f = 1;
  while (!isdigit(c = getchar()))
    if (c == '-') f *= -1;
  do ans = ans * 10 + c - '0';
  while (isdigit(c = getchar()));
  return ans * f;
}
const int N = 200050;
int n, l, k[N];
int val[N], nxt[N], pre[N];
int q1[N], h1, t1, q2[N], h2, t2;
bool cmp(int a, int b) {
  if (val[a] == val[b]) return a < b;
  return val[a] < val[b];
}
int p[N];
long long L[N], R[N], Sl[N], Sr[N];
long long Solve(int v) {
  int m = 0;
  while (true) {
    int a = (h1 < t1 && val[q1[h1]] == v) ? q1[h1] : N;
    int b = (h2 < t2 && val[q2[h2]] == v) ? q2[h2] : N;
    if (a > n && b > n)
      break;
    else if (a < b)
      p[m++] = q1[h1++];
    else
      p[m++] = q2[h2++];
  }
  long long ans = 0;
  p[m] = 0;
  for (int i = 0, j; i < m; i = j + 1) {
    for (j = i; nxt[p[j]] == p[j + 1]; ++j)
      ;
    int u = j - i + 1;
    if (u < l) {
      nxt[pre[p[i]]] = n + 1;
      pre[nxt[p[j]]] = 0;
    } else {
      Sl[0] = L[p[i]];
      Sl[u] = Sr[u] = 0;
      for (int k = 1; k < u; ++k) Sl[k] = Sl[k - 1] + L[p[i + k]];
      for (int k = l - 1; k < u; ++k) ans += R[p[i + k]] * Sl[k - l + 1];
      Sr[u - 1] = L[p[j]];
      for (int k = u - 2; k >= 0; --k) Sr[k] = Sr[k + 1] + R[p[i + k]];
      int u1 = u / l;
      for (int k = 0; k < u1; ++k) {
        int v = p[i + k];
        L[v] = Sl[u - (u1 - k) * l] - (k == 0 ? 0 : Sl[u - (u1 - k + 1) * l]);
        R[v] = Sr[(k + 1) * l - 1] - (k == u1 - 1 ? 0 : Sr[(k + 2) * l - 1]);
        ++val[v];
        q2[t2++] = v;
      }
      Sl[0] = L[p[i]];
      for (int k = 1; k < u1; ++k) Sl[k] = Sl[k - 1] + L[p[i + k]];
      for (int k = l - 1; k < u1; ++k) ans -= R[p[i + k]] * Sl[k - l + 1];
      int a = p[i + u1 - 1], b = nxt[p[j]];
      nxt[a] = b;
      pre[b] = a;
    }
  }
  return ans;
}
int main() {
  n = read(), l = read();
  for (int i = 1; i <= n; ++i) k[i] = i + k[i / l];
  long long ans = 0;
  for (int i = 1; i <= n; ++i) {
    val[q1[i - 1] = i] = read();
    L[i] = R[i] = 1;
    nxt[i] = i + 1;
    pre[i] = i - 1;
  }
  h1 = h2 = t2 = 0;
  t1 = n;
  std::sort(q1, q1 + n, cmp);
  while (h1 < t1 || h2 < t2)
    ans += Solve(std::min(h1 < t1 ? val[q1[h1]] : 0x7f7f7f7f,
                          h2 < t2 ? val[q2[h2]] : 0x7f7f7f7f));
  printf("%lld\n", ans + n);
}
