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

//#define USEPB_DS
#define USETR1
#define CPPELEVEN
#define GPP

/*
 * temp.cpp
 *
 *  Created on: 2012-7-18
 *      Author: BSBandme
 */
//#pragma comment(linker, "/STACK:1024000000,1024000000")

#include <vector>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;

#ifndef CPPELEVEN
#ifdef USETR1
#include <tr1/unordered_map>
#include <tr1/unordered_set>
using namespace tr1;
#endif
#else
#include <unordered_map>
#include <unordered_set>
#endif

#ifdef USEPB_DS
#include <ext/pb_ds/priority_queue.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
// binomial_heap_tag, rc_binomial_heap_tag, thin_heap_tag, binary_heap_tag
typedef __gnu_pbds::priority_queue<int, greater<int>, pairing_heap_tag> pq_type;
// splay_tree_tag, ov_tree_tag
typedef tree <int, null_type, less <int>, rb_tree_tag, tree_order_statistics_node_update> tree_type;
#endif

#define mpr make_pair
typedef unsigned int ui;
typedef unsigned long long ull;
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef pair <double, double> pdd;
typedef vector <int> vi;
typedef vector <ll> vll;
typedef vector <double> vd;
typedef vector <string> vs;
typedef map <string, int> mpsi;
typedef map <double, int> mpdi;
typedef map <int, int> mpii;

const double pi = acos(0.0) * 2.0;
const long double eps = 1e-10;
const int step[8][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}, {-1, 1}, {1, 1}, {1, -1}, {-1, -1}};

template <class T> inline T abs1(T a) {return a < 0 ? -a : a;}

#ifndef CPPELEVEN
template <class T> inline T max1(T a, T b) { return b < a ? a : b; }
template <class T> inline T max1(T a, T b, T c) { return max1(max1(a, b), c); }
template <class T> inline T max1(T a, T b, T c, T d) { return max1(max1(a, b, c), d); }
template <class T> inline T max1(T a, T b, T c, T d, T e) { return max1(max1(a, b, c, d), e); }
template <class T> inline T min1(T a, T b) { return a < b ? a : b; }
template <class T> inline T min1(T a, T b, T c) { return min1(min1(a, b), c); }
template <class T> inline T min1(T a, T b, T c, T d) { return min1(min1(a, b, c), d); }
template <class T> inline T min1(T a, T b, T c, T d, T e) { return min1(min1(a, b, c, d), e); }
#else
template <typename t, typename t1>
t min1(t a, t1 b) { return a < b ? a : b; }
template <typename t, typename... arg>
t min1(t a, arg... arr) { return min1(a, min1(arr...)); }
template <typename t, typename t1>
t max1(t a, t1 b) { return a > b ? a : b; }
template <typename t, typename... arg>
t max1(t a, arg... arr) { return max1(a, max1(arr...)); }
#endif

inline int jud(double a, double b){
  if(abs(a) < eps && abs(b) < eps) return 0;
  else if(abs1(a - b) / max(abs1(a), abs1(b)) < eps) return 0;
  if(a < b) return -1;
  return 1;
}
template <typename t> inline int jud(t a, t b){
  if(a < b) return -1;
  if(a == b) return 0;
  return 1;
}

// f_lb == 1代表返回相同的一串的左边界，f_small == 1代表返回如果没有寻找的值返回小的数
template <typename it, typename t1>
inline int find(t1 val, it a, int na, bool f_small = 1, bool f_lb = 1){
  if(na == 0) return 0;
  int be = 0, en = na - 1;
  if(*a <= *(a + na - 1)){
    if(f_lb == 0) while(be < en){
      int mid = (be + en + 1) / 2;
      if(jud(*(a + mid), val) != 1) be = mid;
      else en = mid - 1;
    }else while(be < en){
      int mid = (be + en) / 2;
      if(jud(*(a + mid), val) != -1) en = mid;
      else be = mid + 1;
    }
    if(f_small && jud(*(a + be), val) == 1) be--;
    if(!f_small && jud(*(a + be), val) == -1) be++;
  } else {
    if(f_lb) while(be < en){
      int mid = (be + en + 1) / 2;
      if(jud(*(a + mid), val) != -1) be = mid;
      else en = mid - 1;
    }else while(be < en){
      int mid = (be + en) / 2;
      if(jud(*(a + mid), val) != 1) en = mid;
      else be = mid + 1;
    }
    if(!f_small && jud(*(a + be), val) == -1) be--;
    if(f_small && jud(*(a + be), val) == 1) be++;
  }
  return be;
}

template <class T> inline T lowb(T num) {return num & (-num); }
#ifdef GPP
inline int bitnum(ui nValue) { return __builtin_popcount(nValue); }
inline int bitnum(int nValue) { return __builtin_popcount(nValue); }
inline int bitnum(ull nValue) { return __builtin_popcount(nValue) + __builtin_popcount(nValue >> 32); }
inline int bitnum(ll nValue) { return __builtin_popcount(nValue) + __builtin_popcount(nValue >> 32); }
inline int bitmaxl(ui a) { if(a == 0) return 0; return 32 - __builtin_clz(a); }
inline int bitmaxl(int a) { if(a == 0) return 0; return 32 - __builtin_clz(a); }
inline int bitmaxl(ull a) { int temp = a >> 32; if(temp) return 32 - __builtin_clz(temp) + 32; return bitmaxl(int(a)); }
inline int bitmaxl(ll a) { int temp = a >> 32; if(temp) return 32 - __builtin_clz(temp) + 32; return bitmaxl(int(a)); }
#else
#endif

long long pow(long long n, long long m, long long mod = 0){
  if(m < 0) return 0;
  long long ans = 1;
  long long k = n;
  while(m){
    if(m & 1) {
      ans *= k;
      if(mod) ans %= mod;
    }
    k *= k;
    if(mod) k %= mod;
    m >>= 1;
  }
  return ans;
}

#define  MOD 1000000007
template <class t1, class t2>
inline void add(t1 &a, t2 b, int mod = -1) {
  if(mod == -1) mod = MOD;
  a += b;
  while(a >= mod) a -= mod;
  while(a < 0) a += mod;
}
template <class t>
void output1(t arr) {
  for(int i = 0; i < (int)arr.size(); i++)
    cerr << arr[i] << ' ';
  cerr << endl;
}
template <class t>
void output2(t arr) {
  for(int i = 0; i < (int)arr.size(); i++)
    output1(arr[i]);
}

//....................密..........封..........线..........下..........禁..........止..........hack...............................................

const int maxn = 200100;
int n, l;
int orig[maxn];
struct Range {
  int from, to;
  vi align_to[2];
  bool operator < (const Range& other) const {
    if (from == other.from) {
      return to < other.to;
    }
    return from < other.from;
  }
} buf[maxn * 3];
int lbuf;
map<int, vector<int>> all_range;
int temp[2][maxn], ltemp;


int main() {
  //............................不要再忘了检查maxn大小了！！！！BSBandme你个SB！！！！........................................
  ios_base::sync_with_stdio(0);
  #ifdef DEBUG //......................................................................................................
  freopen("input.txt", "r", stdin);
  #endif //...........................................................................................................

  scanf("%d%d", &n, &l);
  for (int i = 0; i < n; i++) {
    scanf("%d", orig + i);
    buf[lbuf].from = i;
    buf[lbuf].to = i + 1;
    buf[lbuf].align_to[0].push_back(0);
    buf[lbuf].align_to[1].push_back(0);
    buf[lbuf].align_to[0].push_back(1);
    buf[lbuf].align_to[1].push_back(1);
    all_range[orig[i]].push_back(lbuf++);
  }

  ll ans = 0;
  for (auto& it : all_range) {
    vi& all_r = it.second;
    sort(all_r.begin(), all_r.end(), [&](const int& a, const int& b) {
      return buf[a] < buf[b];
    });
    for (int i = 0, nxt_i = 0; i < (int)all_r.size(); i = nxt_i) {
      while (nxt_i < (int)all_r.size() - 1 &&
          buf[all_r[nxt_i + 1]].from == buf[all_r[nxt_i]].to) {
        nxt_i++;
      }
      nxt_i++;
      ltemp = 1;
      temp[0][0] = temp[1][0] = 0;
      for (int j = i; j < nxt_i; j++) {
        int no = all_r[j];
        auto rbuf = buf[no];
        ltemp--;
        for (int k = 0, rsum = 0; k < (int)rbuf.align_to[0].size(); k++) {
          temp[0][ltemp] += rbuf.align_to[0][k];
          temp[1][ltemp++] += rbuf.align_to[1][rbuf.align_to[0].size() - k - 1];
          if (k >= l) {
            rsum += rbuf.align_to[1][rbuf.align_to[0].size() - k - 1 + l];
          }
          temp[0][ltemp] = temp[1][ltemp] = 0;
          ans -= 1ll * rbuf.align_to[0][k] * rsum;
        }
      }
      for (int j = l, sum = 0; j < ltemp; j++) {
        sum += temp[1][j - l];
        ans += 1ll * temp[0][j] * sum;
      }

      if (ltemp > l) {
        buf[lbuf].from = buf[all_r[i]].from;
        buf[lbuf].to = buf[all_r[nxt_i - 1]].to;
        buf[lbuf].align_to[0].push_back(0);
        buf[lbuf].align_to[1].push_back(0);
        for (int j = l; j < ltemp; j++) {
          if (j % l == 0) {
            buf[lbuf].align_to[0].push_back(0);
            buf[lbuf].align_to[1].push_back(0);
          }
          buf[lbuf].align_to[0].back() += temp[0][j];
          buf[lbuf].align_to[1].back() += temp[1][ltemp - j - 1];
        }
        all_range[it.first + 1].push_back(lbuf++);
      }
    }
  }

  cout << ans + n << endl;

  return 0;
}
