#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
#define int long long
#define PB push_back
#define MP make_pair
#define st first
#define nd second
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((int)(x).size())

using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;
using vll = vector<long long>;
using ld = long double;

#define unordered_map __fast_unordered_map
template<class Key, class Value, class Hash = std::hash<Key>>
using unordered_map = __gnu_pbds::gp_hash_table<Key, Value, Hash>;

template<class C> void mini(C &a4, C b4) { a4 = min(a4, b4); }
template<class C> void maxi(C &a4, C b4) { a4 = max(a4, b4); }

template<class TH> void _dbg(const char *sdbg, TH h){ cerr<<sdbg<<'='<<h<<endl; }
template<class TH, class... TA> void _dbg(const char *sdbg, TH h, TA... a) {
  while(*sdbg!=',')cerr<<*sdbg++;
  cerr<<'='<<h<<','; _dbg(sdbg+1, a...);
}

template<class T> ostream &operator<<(ostream& os, vector<T> V) {
  os << "["; for (auto vv : V) os << vv << ","; return os << "]";
}
template<class L, class R> ostream &operator<<(ostream &os, pair<L,R> P) {
  return os << "(" << P.st << "," << P.nd << ")";
}

#ifdef LOCAL
#define debug(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
#else
#define debug(...) (__VA_ARGS__)
#define cerr if(0)cout
#endif

const int kMaxN = 2e5 + 100;

int n, L;
int vals[kMaxN];


int32_t main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout << fixed << setprecision(11);
  cerr << fixed << setprecision(6);

  cin >> n >> L;
  for (int i = 0; i < n; ++i) {
    cin >> vals[i];
  }

  struct Number {
    int num;
    int lends, rends;
  };

  map<int, Number> nums;
  for (int i = 0; i < n; ++i) {
    nums[i] = Number{vals[i], 1, 1};
  }

  vi order(n);
  iota(ALL(order), 0);
  sort(ALL(order), [&](int lhs, int rhs) {
        return MP(vals[lhs], lhs) < MP(vals[rhs], rhs);
      });

  ll ans = n;
  vector<bool> visited(n);
  map<int, vi> MX;

  for (int lcx : order) {
    if (visited[lcx]) { continue; }
    debug(lcx);
    function<void(int,int)> Consider = [&](int loc, int valval) {
      debug("!", loc, valval);
      auto iter = nums.find(loc);
      if (iter == nums.end()) { return; }
      if (iter->nd.num != valval) { return; }
      //assert(iter->nd.lends == 1 && iter->nd.rends == 1);
      
      vi other_locs;
      auto piter = iter, niter = iter;
      while (piter != nums.begin() && prev(piter)->nd.num == valval) { --piter; }
      while (niter != nums.end() && niter->nd.num == valval) { ++niter; }

      for (auto it = piter; it != niter; ++it) {
        other_locs.PB(it->st);
      }

      const int S = SZ(other_locs);
      debug(other_locs);

      if (S >= L) {

        int rgt = 0;
        int ways_rgt = 0;
        int num_good = !visited[other_locs[0]];
        for (int v : other_locs) { ways_rgt += nums[v].rends; }

        for (int lft = 0; lft + L <= S; ++lft) {
          while (rgt < S && (rgt-lft < L-1 || !num_good)) {
            const int v = other_locs[rgt];
            ways_rgt -= nums[v].rends;
            ++rgt;
            if (rgt < S) { num_good += !visited[other_locs[rgt]]; }
          }
          if (rgt == S) { break; }

          const int ways_lft = nums[other_locs[lft]].lends ;
          debug(lft, rgt, ways_rgt);

          ans += (ll)ways_lft * ways_rgt;
          num_good -= !visited[other_locs[lft]];
        }
      }

      for (int v : other_locs) {
        visited[v] = true;
      }

      vi lends(S), rends(S);
      for (int i = 0; i < S; ++i) {
        lends[i] = nums[other_locs[i]].lends;
        rends[i] = nums[other_locs[i]].rends;
      }

      for (int v : other_locs) { nums.erase(v); }
      const int num_add = S / L;
      vector<Number> xs(num_add);
      for (int idx_add = 0; idx_add < num_add; ++idx_add) {
        xs[idx_add].num = valval + 1;

        const int lft = (idx_add + 1) * L - 1;
        const int rgt = min(S, (idx_add + 2) * L - 1);
        for (int i = lft; i < rgt; ++i) {
          xs[idx_add].rends += rends[i];
          xs[num_add - idx_add - 1].lends += lends[S - i - 1];
        }
      }


      for (int idx_add = 0; idx_add < num_add; ++idx_add) {
        debug(idx_add, xs[idx_add].num, xs[idx_add].lends, xs[idx_add].rends);
        nums.emplace(other_locs[0] + idx_add, xs[idx_add]);
      }

      if (num_add == 0) {
        Number dummy{(int)2e9, 0, 0};
        nums[other_locs[0]] = dummy;
      } else {
        debug(other_locs[0], num_add);
        MX[xs[0].num].push_back(other_locs[0]);
      }
    };

    while (!MX.empty() && MX.begin()->st < vals[lcx]) {
      auto v = MX.begin()->nd;
      int t = MX.begin()->st;
      MX.erase(MX.begin());
      for (int loc : v) { Consider(loc, t); }
    }
    Consider(lcx, vals[lcx]);
  }

  cout << ans << "\n";
}



Measured memory_bytes: 21520