#include <bits/stdc++.h>
using namespace std;
template <typename A, typename B>
string to_string(pair<A, B> p);
template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p);
template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p);
string to_string(const string &s) { return '"' + s + '"'; }
string to_string(const char *s) { return to_string((string)s); }
string to_string(bool b) { return (b ? "true" : "false"); }
string to_string(vector<bool> v) {
  bool first = true;
  string res = "{";
  for (int i = 0; i < static_cast<int>(v.size()); i++) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(v[i]);
  }
  res += "}";
  return res;
}
template <size_t N>
string to_string(bitset<N> v) {
  string res = "";
  for (size_t i = 0; i < N; i++) {
    res += static_cast<char>('0' + v[i]);
  }
  return res;
}
template <typename A>
string to_string(A v) {
  bool first = true;
  string res = "{";
  for (const auto &x : v) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(x);
  }
  res += "}";
  return res;
}
template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p) {
  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " +
         to_string(get<2>(p)) + ")";
}
template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p) {
  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " +
         to_string(get<2>(p)) + ", " + to_string(get<3>(p)) + ")";
}
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}
class segtree {
 public:
  struct node {
    int sum = 0;
    void apply(int l, int r, int v, bool SET = false) {
      if (SET) {
        sum = v;
      } else {
        sum += v;
      }
    }
  };
  node unite(const node &a, const node &b) const {
    node res;
    res.sum = a.sum + b.sum;
    return res;
  }
  inline void push(int x, int l, int r) {}
  inline void pull(int x, int z) { tree[x] = unite(tree[x + 1], tree[z]); }
  int n;
  vector<node> tree;
  void build(int x, int l, int r) {
    if (l == r) {
      return;
    }
    int y = (l + r) >> 1;
    int z = x + ((y - l + 1) << 1);
    build(x + 1, l, y);
    build(z, y + 1, r);
    pull(x, z);
  }
  template <typename M>
  void build(int x, int l, int r, const vector<M> &v) {
    if (l == r) {
      tree[x].apply(l, r, v[l]);
      return;
    }
    int y = (l + r) >> 1;
    int z = x + ((y - l + 1) << 1);
    build(x + 1, l, y, v);
    build(z, y + 1, r, v);
    pull(x, z);
  }
  node get(int x, int l, int r, int ll, int rr) {
    if (ll <= l && r <= rr) {
      return tree[x];
    }
    int y = (l + r) >> 1;
    int z = x + ((y - l + 1) << 1);
    push(x, l, r);
    node res{};
    if (rr <= y) {
      res = get(x + 1, l, y, ll, rr);
    } else {
      if (ll > y) {
        res = get(z, y + 1, r, ll, rr);
      } else {
        res = unite(get(x + 1, l, y, ll, rr), get(z, y + 1, r, ll, rr));
      }
    }
    pull(x, z);
    return res;
  }
  template <typename... M>
  void modify(int x, int l, int r, int ll, int rr, const M &...v) {
    if (ll <= l && r <= rr) {
      tree[x].apply(l, r, v...);
      return;
    }
    int y = (l + r) >> 1;
    int z = x + ((y - l + 1) << 1);
    push(x, l, r);
    if (ll <= y) {
      modify(x + 1, l, y, ll, rr, v...);
    }
    if (rr > y) {
      modify(z, y + 1, r, ll, rr, v...);
    }
    pull(x, z);
  }
  int find_first_knowingly(int x, int l, int r,
                           const function<bool(const node &)> &f) {
    if (l == r) {
      return l;
    }
    push(x, l, r);
    int y = (l + r) >> 1;
    int z = x + ((y - l + 1) << 1);
    int res;
    if (f(tree[x + 1])) {
      res = find_first_knowingly(x + 1, l, y, f);
    } else {
      res = find_first_knowingly(z, y + 1, r, f);
    }
    pull(x, z);
    return res;
  }
  int find_first(int x, int l, int r, int ll, int rr,
                 const function<bool(const node &)> &f) {
    if (ll <= l && r <= rr) {
      if (!f(tree[x])) {
        return -1;
      }
      return find_first_knowingly(x, l, r, f);
    }
    push(x, l, r);
    int y = (l + r) >> 1;
    int z = x + ((y - l + 1) << 1);
    int res = -1;
    if (ll <= y) {
      res = find_first(x + 1, l, y, ll, rr, f);
    }
    if (rr > y && res == -1) {
      res = find_first(z, y + 1, r, ll, rr, f);
    }
    pull(x, z);
    return res;
  }
  int find_last_knowingly(int x, int l, int r,
                          const function<bool(const node &)> &f) {
    if (l == r) {
      return l;
    }
    push(x, l, r);
    int y = (l + r) >> 1;
    int z = x + ((y - l + 1) << 1);
    int res;
    if (f(tree[z])) {
      res = find_last_knowingly(z, y + 1, r, f);
    } else {
      res = find_last_knowingly(x + 1, l, y, f);
    }
    pull(x, z);
    return res;
  }
  int find_last(int x, int l, int r, int ll, int rr,
                const function<bool(const node &)> &f) {
    if (ll <= l && r <= rr) {
      if (!f(tree[x])) {
        return -1;
      }
      return find_last_knowingly(x, l, r, f);
    }
    push(x, l, r);
    int y = (l + r) >> 1;
    int z = x + ((y - l + 1) << 1);
    int res = -1;
    if (rr > y) {
      res = find_last(z, y + 1, r, ll, rr, f);
    }
    if (ll <= y && res == -1) {
      res = find_last(x + 1, l, y, ll, rr, f);
    }
    pull(x, z);
    return res;
  }
  segtree(int _n) : n(_n) {
    assert(n > 0);
    tree.resize(2 * n - 1);
    build(0, 0, n - 1);
  }
  template <typename M>
  segtree(const vector<M> &v) {
    n = v.size();
    assert(n > 0);
    tree.resize(2 * n - 1);
    build(0, 0, n - 1, v);
  }
  node get(int ll, int rr) {
    assert(0 <= ll && ll <= rr && rr <= n - 1);
    return get(0, 0, n - 1, ll, rr);
  }
  node get(int p) {
    assert(0 <= p && p <= n - 1);
    return get(0, 0, n - 1, p, p);
  }
  template <typename... M>
  void modify(int ll, int rr, const M &...v) {
    assert(0 <= ll && ll <= rr && rr <= n - 1);
    modify(0, 0, n - 1, ll, rr, v...);
  }
  int find_first(int ll, int rr, const function<bool(const node &)> &f) {
    assert(0 <= ll && ll <= rr && rr <= n - 1);
    return find_first(0, 0, n - 1, ll, rr, f);
  }
  int find_last(int ll, int rr, const function<bool(const node &)> &f) {
    assert(0 <= ll && ll <= rr && rr <= n - 1);
    return find_last(0, 0, n - 1, ll, rr, f);
  }
};
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, k;
  cin >> n >> k;
  vector<int> a(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  vector<int> vals;
  for (int i = 0; i < n; i++) {
    vals.push_back(a[i]);
  }
  sort(vals.begin(), vals.end());
  vals.resize(unique(vals.begin(), vals.end()) - vals.begin());
  segtree segt((int)vals.size());
  auto Modify = [&](int at, int delta, bool SET = false) {
    auto it = lower_bound(vals.begin(), vals.end(), at);
    if (it != vals.end() && *it == at) {
      int pos = (int)(it - vals.begin());
      segt.modify(pos, pos, delta, SET);
    }
  };
  vector<int> st;
  vector<int> ends;
  vector<int> good;
  long long ans = 0;
  map<int, int> how_many;
  map<int, set<int>> at;
  set<pair<int, int>> segs;
  for (int itt = 0; itt < n; itt++) {
    int x = a[itt];
    while (!st.empty() && x > st.back()) {
      int val = st.back();
      int cnt = 0;
      for (int j = (int)st.size() - 1; j >= 0; j--) {
        if (st[j] != val) {
          break;
        }
        ++cnt;
      }
      if (cnt < k) {
        for (int y : st) {
          Modify(y, 0, true);
        }
        st.clear();
        ends.clear();
        good.clear();
        how_many.clear();
        at.clear();
        break;
      }
      for (int i = 0; i < k - 1; i++) {
        if (good.back()) {
          Modify(st.back(), -ends.back());
        }
        st.pop_back();
        ends.pop_back();
        good.pop_back();
        --cnt;
      }
      vector<int> to_push;
      while (cnt > 0) {
        int sum = 0;
        for (int i = 0; i < k && cnt > 0; i++) {
          sum += ends.back();
          if (good.back()) {
            Modify(st.back(), -ends.back());
          }
          st.pop_back();
          ends.pop_back();
          good.pop_back();
          --cnt;
        }
        to_push.push_back(sum);
      }
      while (!to_push.empty()) {
        st.push_back(val + 1);
        ends.push_back(to_push.back());
        good.push_back(0);
        at[st.back()].insert((int)st.size() - 1);
        to_push.pop_back();
      }
      at[val].clear();
      assert(how_many[val] >= k);
      how_many.erase(val);
      auto it = segs.lower_bound({val + 1, -1});
      assert(it != segs.begin());
      --it;
      auto p = *it;
      assert(p.first <= val && val <= p.second);
      segs.erase(it);
      if (p.first < val) {
        segs.emplace(p.first, val - 1);
      }
      if (val < p.second) {
        segs.emplace(val + 1, p.second);
      }
    }
    while ((int)at[x].size() >= k) {
      int pos = *at[x].begin();
      at[x].erase(at[x].begin());
      Modify(x, ends[pos]);
      good[pos] = 1;
    }
    st.push_back(x);
    ends.push_back(1);
    good.push_back(0);
    at[st.back()].insert((int)st.size() - 1);
    int ptr = x;
    while (true) {
      int u = ++how_many[ptr];
      if (u == k) {
        int val = ptr;
        int L = val;
        int R = val;
        auto it = segs.lower_bound({val + 1, -1});
        if (it != segs.end() && it->first == val + 1) {
          R = it->second;
          it = segs.erase(it);
        }
        if (it != segs.begin() && prev(it)->second == val - 1) {
          L = prev(it)->first;
          segs.erase(prev(it));
        }
        segs.emplace(L, R);
      }
      if (u >= k) {
        if (!at[ptr].empty()) {
          int pos = *at[ptr].begin();
          at[ptr].erase(at[ptr].begin());
          Modify(ptr, ends[pos]);
          good[pos] = 1;
        }
      }
      if (u % k == 0) {
        ++ptr;
      } else {
        break;
      }
    }
    int val = x;
    auto it = segs.lower_bound({val + 1, -1});
    int up_to = x;
    if (it != segs.begin()) {
      --it;
      auto p = *it;
      if (p.first <= val && val <= p.second) {
        up_to = p.second + 1;
      }
    }
    int z =
        (int)(lower_bound(vals.begin(), vals.end(), up_to + 1) - vals.begin());
    long long real_total = (z == 0 ? 0 : segt.get(0, z - 1).sum);
    ans += real_total + 1;
  }
  cout << ans << '\n';
  return 0;
}
