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
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cassert>
#define FILL(a, n, x) memset((a), (x), sizeof ((a)[0]) * (n))
#define FILLA(a, x) memset((a), (x), sizeof (a))
#define COPY(a, n, b) memcpy((b), (a), sizeof ((a)[0]) * (n))
#define COPYA(a, b) memcpy((b), (a), sizeof (a))
using namespace std;

typedef pair<int, int> pii;
typedef long long li;
typedef unsigned long long lu;
const int inf = ~0U >> 2;
const li infl = ~0LLU >> 2;

template <class T> inline void Min(T &x, T y) { if (y < x) x = y; }
template <class T> inline void Max(T &x, T y) { if (y > x) x = y; }

// const int mod = 1e9 + 7;
// inline int Add(int x) { return x >= mod ? x - mod : x; }
// inline void Add(int &x, int y) { x += y; if (x >= mod) x -= mod; }
// inline int Sub(int x) { return x < 0 ? x + mod : x; }
// inline void Sub(int &x, int y) { x -= y; if (x < 0) x += mod; }
// inline int Mul(int x, int y) { return (int)((li)x * y % mod); }
// inline int Mul(int x, int y, int z) { return Mul(x, Mul(y, z)); }
// int Pow(int x, int y) { int z = 1;
//   for (; y; y >>= 1, x = Mul(x, x)) { if (y & 1) z = Mul(z, x); } return z; }
// inline int Inv(int x) { return Pow(x, mod - 2); }
// inline int Fix(li x) { x %= mod; if (x < 0) x += mod; return (int)x; }
// inline int Fix(int x) { x %= mod; if (x < 0) x += mod; return x; }

// ----------------------------------------

const int maxn = 2e5;

int n, lim;
int st[maxn], top;
int L[maxn], R[maxn];
li ans;

li Ways(int l, int r) {
  li sum = 0, tot = 0;
  for (int i = r - 1; i >= l + lim - 1; --i) {
    sum += R[i];
    tot += (li)L[i - lim + 1] * sum;
  }
  for (int i = l; i < r; ++i) {
    tot += (li)L[i] * R[i];
  }
  return tot;
}

void Merge(void) {
  int val = st[top - 1];
  int begin = top - 1;
  while (begin > 0 && st[begin - 1] == st[begin]) {
    --begin;
  }
  int end = top;
  ans += Ways(begin, end);

  if (end - begin < lim) {
    top = begin;
    while (top > 0) Merge();
    return;
  }
  int len = (end - begin) / lim;

  static int cntP[maxn + 1], cntS[maxn + 1];
  FILL(cntP, len + 1, 0);
  FILL(cntS, len + 1, 0);
  for (int i = begin; i < end; ++i) {
    int c = i - begin + 1;
    if (c >= lim) {
      cntP[c / lim] += R[i];
    }
    c = end - i;
    if (c >= lim) {
      cntS[c / lim] += L[i];
    }
  }
  top = begin + len;
  for (int i = 0; i < len; ++i) {
    st[begin + i] = val + 1;
    L[begin + i] = cntS[len - i];
    R[begin + i] = cntP[i + 1];
  }

  ans -= Ways(begin, top);
}

int main(void) {
  scanf("%d%d", &n, &lim);
  top = 0;
  ans = 0;
  for (int i = 0; i < n; ++i) {
    int now;
    scanf("%d", &now);
    while (top > 0 && st[top - 1] < now) {
      Merge();
    }
    L[top] = R[top] = 1;
    st[top++] = now;
  }
  while (top > 0) {
    Merge();
  }
  printf("%lld\n", ans);
  return 0;
}
