#include <bits/stdc++.h>
using namespace std;
namespace fastIO1 {
inline char read() {
  static const int IN_LEN = 1000000;
  static char buf[IN_LEN], *s, *t;
  return (s == t               ? t = (s = buf) + fread(buf, 1, IN_LEN, stdin),
          (s == t ? -1 : *s++) : *s++);
}
template <class T>
inline void read(T &x) {
  static bool iosig;
  static char c;
  for (iosig = false, c = read(); !isdigit(c); c = read()) {
    if (c == '-') iosig = true;
    if (c == -1) return;
  }
  for (x = 0; isdigit(c); c = read()) x = ((x + (x << 2)) << 1) + (c ^ '0');
  if (iosig) x = -x;
}
inline char readc(char &c) {
  for (c = read(); !isalpha(c) && !isdigit(c); c = read())
    if (c == -1) return 0;
}
const int OUT_LEN = 10000000;
char obuf[OUT_LEN], *ooh = obuf;
inline void print(char c) {
  if (ooh == obuf + OUT_LEN) fwrite(obuf, 1, OUT_LEN, stdout), ooh = obuf;
  *ooh++ = c;
}
template <class T>
inline void print(T x) {
  static int buf[30], cnt;
  if (x == 0)
    print('0');
  else {
    if (x < 0) print('-'), x = -x;
    for (cnt = 0; x; x /= 10) buf[++cnt] = x % 10 + 48;
    while (cnt) print((char)buf[cnt--]);
  }
}
inline void flush() { fwrite(obuf, 1, ooh - obuf, stdout); }
}  // namespace fastIO1
namespace fastIO2 {
template <class T>
inline void read(T &x) {
  static bool iosig;
  static char c;
  for (iosig = false, c = getchar(); !isdigit(c); c = getchar()) {
    if (c == '-') iosig = true;
    if (c == -1) return;
  }
  for (x = 0; isdigit(c); c = getchar()) x = ((x + (x << 2)) << 1) + (c ^ '0');
  if (iosig) x = -x;
}
}  // namespace fastIO2
using namespace fastIO1;
int n, m, now, a[(100010)];
pair<int, int> pos[(100010)];
long long ans;
vector<pair<pair<int, int>, pair<int, int> > > t, tmp;
vector<pair<int, int> > wk, pp;
int calc(vector<pair<int, int> > &a) {
  long long sum = 0, ans = 0;
  for (int i = 0, j = m - 1; j < a.size(); i++, j++)
    sum += a[i].first, ans += sum * a[j].second;
  return ans;
}
int main() {
  read(n), read(m), ans = n;
  for (int i = 1; i <= n; i++) read(a[i]), pos[i] = make_pair(a[i], i);
  sort(pos + 1, pos + n + 1);
  for (int p = 1, val = 0; p <= n || !t.empty();) {
    cout << p << endl;
    if (t.empty())
      val = pos[p].first;
    else
      val++;
    for (; pos[p].first == val; p++)
      t.emplace_back(make_pair(pos[p].second, pos[p].second), make_pair(1, 1));
    tmp.clear(), sort(t.begin(), t.end());
    for (int i = 0, j = 0; i < t.size(); i = j + 1) {
      for (j = i;
           j + 1 < t.size() && t[j + 1].first.first == t[j].first.second + 1;
           j++)
        ;
      int len = j - i + 1, cnt = len / m;
      if (cnt) {
        wk.clear();
        for (int k = i; k <= j; k++) wk.push_back(t[k].second);
        ans += calc(wk), wk.clear(), wk.resize(cnt), pp.clear();
        for (int k = 1; k <= cnt; k++)
          pp.emplace_back(
              t[i].first.first + k - 1,
              (k == cnt) ? t[j].first.second : t[i].first.first + k - 1);
        for (int k = i; k <= j; k++) {
          int l = k - i + 1, r = j - k + 1;
          if (l >= m) wk[l / m - 1].second += t[k].second.second;
          if (r >= m) wk[cnt - r / m].first += t[k].second.first;
        }
        ans -= calc(wk);
        for (int k = 0; k < pp.size(); k++) tmp.emplace_back(pp[k], wk[k]);
      }
    }
    t = tmp;
  }
  cout << ans;
}
