#include <bits/stdc++.h>
using namespace std;
inline int read() {
  int x = 0, f = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  return x * f;
}
struct Data {
  int l, r, x;
  vector<int> sl, sr;
};
vector<Data> s[4000000 + 5];
int n, K, a[200000 + 5], c[4000000 + 5], num, f[200000 + 5];
long long ans;
bool cmp(const Data& x, const Data& y) { return x.l < y.l; }
int main() {
  ans = n = read();
  K = read();
  for (int i = 1; i <= n; ++i) {
    a[i] = read();
    for (int t = n, j = 0; t; t /= K, ++j) c[++num] = a[i] + j;
  }
  sort(c + 1, c + num + 1);
  num = unique(c + 1, c + num + 1) - c - 1;
  for (int i = 1, j; i <= n; i = j + 1) {
    int v = lower_bound(c + 1, c + num + 1, a[i]) - c;
    for (j = i; j < n && a[j + 1] == a[j]; ++j)
      ;
    Data nx;
    nx.x = 1;
    nx.sl.push_back(0);
    nx.sr.push_back(0);
    for (int k = i; k <= j; ++k) {
      nx.l = nx.r = k;
      nx.sl[0] = nx.sr[0] = k;
      s[v].push_back(nx);
    }
  }
  for (int k = 1; k <= num; ++k)
    if (s[k].size()) {
      sort(s[k].begin(), s[k].end(), cmp);
      int N = s[k].size();
      for (int i = 0, j; i < N; i = j + 1) {
        int tot = s[k][i].x, cnt = 0, last = 0;
        for (j = i; j + 1 < N && s[k][j + 1].l == s[k][j].r + 1;)
          ++j, tot += s[k][j].x;
        if (tot < K) continue;
        for (int l = i; l <= j; ++l)
          for (int g = s[k][l].x - 1; ~g; --g)
            ++cnt, f[cnt] = f[cnt - 1] + s[k][l].sr[g] -
                            (g + 1 < s[k][l].x ? s[k][l].sr[g + 1]
                                               : (l == i ? s[k][l].l - 1
                                                         : s[k][l - 1].sr[0]));
        cnt = 0;
        for (int l = i; l <= j; ++l)
          for (int g = 0; g < s[k][l].x; ++g) {
            ++cnt;
            if (s[k][l].l == s[k][l].r) last = cnt;
            if (cnt >= K)
              ans +=
                  1LL *
                  ((g + 1 < s[k][l].x ? s[k][l].sl[g + 1] : (s[k][l].r + 1)) -
                   s[k][l].sl[g]) *
                  f[min(last, cnt - K + 1)];
          }
        Data nx;
        nx.l = s[k][i].l, nx.r = s[k][j].r;
        nx.x = tot / K;
        cnt = 0;
        for (int l = i; l <= j; ++l)
          for (int g = 0; g < s[k][l].x; ++g) {
            ++cnt;
            if (cnt % K == 0) nx.sl.push_back(s[k][l].sl[g]);
          }
        cnt = 0;
        for (int l = j; l >= i; --l)
          for (int g = 0; g < s[k][l].x; ++g) {
            ++cnt;
            if (cnt % K == 0) nx.sr.push_back(s[k][l].sr[g]);
          }
        s[k + 1].push_back(nx);
      }
    }
  cout << ans;
  return 0;
}
