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 <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...);}

#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

#define set0(x) memset(x,0,sizeof(x))
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<ll> vll;
template<typename T> void read(T &x){
    x = 0;char ch = getchar();ll f = 1;
    while(!isdigit(ch)){if(ch == '-')f*=-1;ch=getchar();}
    while(isdigit(ch)){x = x*10+ch-48;ch=getchar();}x*=f;
}
template<typename T, typename... Args> void read(T &first, Args& ... args) {
    read(first);
    read(args...);
}

int n,k,cc;
ll ans = 0;
template<class T>
struct RMQ {
    vector<vector<T>> jmp;
    RMQ(const vector<T>& V) : jmp(1, V) {
        for (int pw = 1, k = 1; pw * 2 <= sz(V); pw *= 2, ++k) {
            jmp.emplace_back(sz(V) - pw * 2 + 1);
            rep(j,0,sz(jmp[k]))
            jmp[k][j] = max(jmp[k - 1][j], jmp[k - 1][j + pw]);
        }
    }
    T query(int a, int b) {
        assert(a < b); // or return inf if a == b
        int dep = 31 - __builtin_clz(b - a);
        return max(jmp[dep][a], jmp[dep][b - (1 << dep)]);
    }
};
set<pii> S;
#define CAT(A,B)  A.insert(A.end(),all(B))
struct ret{
    vll val,L,R;
    void absorb(ret rhs){
        CAT(val,rhs.val);
        CAT(L,rhs.L);
        CAT(R,rhs.R);
    }
};
vector<int> A(1,0);
RMQ<int> Q(A);
ll calc(ret &C){
    ll cr = 0;
    int c = 0;
    while(c<C.val.size()){
        int d = c,cu = 0;
        while(d<C.val.size() && C.val[d]!=-1){
            if(d>c+k-2)cu+=C.R[d];
            d++;
        }
        for(int i=c;i<d;i++){
            cr = cr+C.L[i]*C.R[i];
            cr = cr+1ll*cu*C.L[i];
            if(i+k-1<d){
                cu-=C.R[i+k-1];
            }
        }
        c = d+1;
    }
    return cr;
}
ret solve(int l,int r,int ep){
    if(l>r)return ret();
    int p = l,cmx = Q.query(l,r+1);
    ret C,I;I.val.PB(cmx);I.R.PB(1);I.L.PB(1);
    while(p<=r){
        int nxt = S.lower_bound(MP(cmx,p))->second;
        if(nxt>r){
            C.absorb(solve(p,r,cmx));
            break;
        }else{
            C.absorb(solve(p,nxt-1,cmx));
            C.absorb(I);
            p = nxt+1;
        }
    }
    /*
    cout<<"["<<l<<' '<<r<<' '<<cmx<<"]"<<endl;
    debug(C.val);
    debug(C.L);
    debug(C.R);*/
    ans+=calc(C);
    if(ep-cmx>25 || pow(1.0*k,ep-cmx)>2*(r-l+1) || pow(k,ep-cmx)>C.val.size()){
        I.val[0] = -1;
        return I;
    }
    int req = 1;for(int i=0;i<ep-cmx;i++)req*=k;
    int cnt = 0;
    for(auto ct:C.val)if(ct == -1)cnt+=1;
    ret CR;
    if(cnt){
        vll L,R;
        for(int i=0;C.val[i] == cmx;i++){
            if((i+1)/req!=0){
                int cp = (i+1)/req-1;
                if(R.size()<cp+1)R.PB(0);
                R[cp]+=C.R[i];
            }
        }
        for(int i=0;C.val[C.val.size()-1-i] == cmx;i++){
            if((i+1)/req!=0){
                int cp = (i+1)/req-1;
                if(L.size()<cp+1)L.PB(0);
                L[cp]+=C.L[C.L.size()-1-i];
            }
        }
        for(int i=0;i<R.size();i++){
            CR.R.PB(R[i]);
            CR.L.PB(0);
            CR.val.PB(ep);
        }
        CR.R.PB(0);
        CR.L.PB(0);
        CR.val.PB(-1);
        for(int i=0;i<L.size();i++){
            CR.R.PB(0);
            CR.L.PB(L[L.size()-1-i]);
            CR.val.PB(ep);
        }
    }else{
        int cul = C.val.size()/req;
        CR.val = vll(cul,ep);
        CR.L = vll(cul,0);
        CR.R = vll(cul,0);
        for(int i=req;i<=C.val.size();i++){
            CR.R[i/req-1]+=C.R[i-1];
            CR.L[cul-i/req]+=C.L[C.val.size()-i];
        }
    }
    ans-=calc(CR);
    /*
    cout<<"["<<l<<' '<<r<<' '<<ep<<"]"<<endl;
    debug(CR.val);
    debug(CR.L);
    debug(CR.R);*/
    return CR;
}
int main() {
    read(n,k);
    for(int i=1;i<=n;i++){
        read(cc);
        A.PB(cc);
        S.insert(MP(cc,i));
        S.insert(MP(cc,1e9));
    }
    Q = RMQ<int>(A);
    solve(1,n,1e9+1);
    cout<<ans<<endl;
    return 0;
}
