For a sequence S of positive integers and positive integers k and l, S is said to belong to level (k,l) when one of the following conditions is satisfied:

* The length of S is 1, and its only element is k.
* There exist sequences T_1,T_2,...,T_m (m \geq l) belonging to level (k-1,l) such that the concatenation of T_1,T_2,...,T_m in this order coincides with S.



Note that the second condition has no effect when k=1, that is, a sequence belongs to level (1,l) only if the first condition is satisfied.

Given are a sequence of positive integers A_1,A_2,...,A_N and a positive integer L. Find the number of subsequences A_i,A_{i+1},...,A_j (1 \leq i \leq j \leq N) that satisfy the following condition:

* There exists a positive integer K such that the sequence A_i,A_{i+1},...,A_j belongs to level (K,L).

Constraints

* 1 \leq N \leq 2 \times 10^5
* 2 \leq L \leq N
* 1 \leq A_i \leq 10^9

Input

Input is given from Standard Input in the following format:


N L
A_1 A_2 ... A_N


Output

Print the number of subsequences A_i,A_{i+1},...,A_j (1 \leq i \leq j \leq N) that satisfy the condition.

Examples

Input

9 3
2 1 1 1 1 1 1 2 3


Output

22


Input

9 2
2 1 1 1 1 1 1 2 3


Output

41


Input

15 3
4 3 2 1 1 1 2 3 2 2 1 1 1 2 2


Output

31
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// using namespace __gnu_pbds;
// gp_hash_table<int, int> mapka;

using namespace std;
#define PB push_back
#define MP make_pair
#define LL long long
#define int LL
#define FOR(i,a,b) for(int i = (a); i <= (b); i++)
#define RE(i,n) FOR(i,1,n)
#define REP(i,n) FOR(i,0,(int)(n)-1)
#define R(i,n) REP(i,n)
#define VI vector<int>
#define PII pair<int,int>
#define LD long double
#define FI first
#define SE second
#define st FI
#define nd SE
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((int)(x).size())

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 MAX = 200100;
int n,l;

int nast[MAX];
int pop[MAX];
vector<int> pref[MAX];
vector<int> suf[MAX];
int val[MAX];
int kr[MAX];
set<PII> secik;
int res = 0;
int32_t main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout << fixed << setprecision(11);
  cerr << fixed << setprecision(6);
  cin >> n >> l;
  res = 0;
  R(i,n){
    nast[i] = i + 1;
    pop[i] = i - 1;
    cin >> val[i];
    pref[i] = {1};
    suf[i] = {1};
    kr[i] = 1;
    secik.insert({val[i],i});
  }
  while(SZ(secik)){
    int id = secik.begin()->SE;
    secik.erase(secik.begin());
    if(val[id] == -1)continue;
    int va = val[id];
    vector<int> gd;
    int ak = id;
    while(ak != n && val[ak] == va){
      gd.PB(ak);
      val[ak] = -1;
      ak = nast[ak];
    }
    int m = SZ(gd);
    {
      int i = 0;
      int ii = SZ(suf[gd[i]]);
      int wcze = 0;
      int mam = 0;
      for(int j = 1; j < m; j++){
        R(jj,SZ(pref[gd[j]])){
          while(i != j && ii + jj + mam + 1 >= l){
            ii--;
            wcze += suf[gd[i]][ii];
            if(ii == 0){
              i++;
              mam -= kr[gd[i]];
              ii = SZ(suf[gd[i]]);
            }
          }
          res += pref[gd[j]][jj] * wcze;
//           debug(res,wcze,j,jj,i,ii,mam,pref[gd[j]][jj]);
        }
        mam += kr[gd[j]];
      }
    }
    R(i,m){
      debug(val[gd[i]],kr[gd[i]],pref[gd[i]],suf[gd[i]]);
    }
    debug(res);
    
    
    vector<int> preff;
    int all = 0;
    R(i,m){
      R(ii,SZ(pref[gd[i]])){
        all ++;
        if(all % l == 0)
          preff.PB(0);
        if(SZ(preff))
          preff.back() += pref[gd[i]][ii];
      }
    }
    debug(preff);
    
    
    if(nast[gd.back()] != n){
      pop[nast[id]] = id;
    }
    nast[id] = nast[gd.back()];
    
    if(SZ(preff)){
      pref[id] = preff;
      kr[id] = SZ(preff);
      
      vector<int> suff;
      all = 0;
      for(int i = m - 1; i >= 0; i--){
        R(ii,SZ(suf[gd[i]])){
          all ++;
          if(all % l == 0)
            suff.PB(0);
          if(SZ(suff))
            suff.back() += suf[gd[i]][ii];
        }
      }
      
      val[id] = va + 1;
      suf[id] = suff;
      secik.insert({val[id],id});
    }
  }
  cout << res + n << "\n";
}
