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;

typedef long long ll;

const int MAX_N = 2e5 + 10, MAX_LOG_N = 40;

int N, L, M, A[MAX_N], rnk[MAX_N], height[MAX_N];
ll powL[MAX_LOG_N], ans;
vector<int> ltor[MAX_N], rtol[MAX_N];
int segmax[MAX_N];

struct DSU {
    int pa[MAX_N], lb[MAX_N], rb[MAX_N];

    int find(int x) { return pa[x] == x ? x : pa[x] = find(pa[x]); }

    int lbound(int x) { return lb[find(x)]; }

    int rbound(int x) { return rb[find(x)]; }

    void init(int n) {
        for (int i = 1; i <= n; i++) pa[i] = lb[i] = rb[i] = i;
    }

    void merge(int a, int b) {
        a = find(a); b = find(b);
        pa[a] = b;
        rb[b] = max(rb[a], rb[b]);
        lb[b] = min(lb[a], lb[b]);
    }
} dsu;

bool adjacent(int a, int b) {
    if (a > b) swap(a, b);
    if (b - a == 1) return true;
    return A[a + 1] <= A[a] && dsu.find(a + 1) == dsu.find(b - 1);
}

void init() {
    scanf("%d%d", &N, &L); ans = N;
    powL[0] = 1;
    while (powL[M] * L <= N) powL[M + 1] = powL[M] * L, M++;
    for (int i = 1; i <= N; i++) scanf("%d", &A[i]);
    for (int i = 1; i <= N; i++) rnk[i] = i;
    sort(rnk + 1, rnk + N + 1, [](const int &lhs, const int &rhs) {
                                   if (A[lhs] != A[rhs]) return A[lhs] < A[rhs];
                                   return lhs < rhs;
                               });
    dsu.init(N);
}

void get_ans(int lb, int rb, const vector<int> &walls) {
    int wh = A[walls.front()];
    list<int> pending;
    int lcnt = 0;
    auto add = [&](int x){
                   pending.push_back(x);
                   if (pending.size() >= L) {
                       lcnt += pending.front();
                       pending.pop_front();
                   }
               };

    auto eraseAll = [&]{
                        pending.clear();
                        lcnt = 0;
                    };
    if (walls.front() != lb) {
        int x = dsu.find(lb);
        int h = height[x];
        if (wh - h <= M) {
            int r = powL[wh - h];
            vector<int> t;
            for (int i = 1; i <= rtol[x].size(); i++) {
                if (i < r) continue;
                if (i % r == 0) t.push_back(0);
                t.back() += rtol[x][i - 1];
            }
            for (int i = t.size() - 1; i >= 0; i--)
                add(t[i]);
        }
    }
    for (int wall : walls) {
        add(1);
        vector<int> tr;
        tr.push_back(1);
        int x = wall + 1;
        if (x <= rb && A[x] != wh) {
            x = dsu.find(x);
            int h = height[x];
            if (wh - h <= M) {
                int r = powL[wh - h];
                for (int i = 1; i <= ltor[x].size(); i++) {
                    if (i < r) continue;
                    if (i % r == 0) tr.push_back(0);
                    tr.back() += ltor[x][i - 1];
                }
            }
        }
        ll tcnt = lcnt;
        list<int>::iterator j = pending.begin();
        for (int i = 0; i < tr.size(); i++) {
            ans += tr[i] * tcnt;
            if (i + 1 + pending.size() >= L && j != pending.end()) {
                tcnt += *j;
                j++;
            }
        }
        if (x <= rb && A[x] != wh) {
            int h = height[x];
            if (wh - h <= M) {
                int r = powL[wh - h];
                if (segmax[x] < r) eraseAll();
                vector<int> t;
                for (int i = 1; i <= rtol[x].size(); i++) {
                    if (i < r) continue;
                    if (i % r == 0) t.push_back(0);
                    t.back() += rtol[x][i - 1];
                }
                for (int i = t.size() - 1; i >= 0; i--)
                    add(t[i]);
            } else eraseAll();
        }
    }
}

vector<int> get_ltor(int lb, int rb, const vector<int> &walls) {
    int wh = A[walls.front()];
    vector<int> res;
    if (lb != walls.front()) {
        int x = dsu.find(lb);
        int h = height[x];
        if (wh - h > M) return res;
        int r = powL[wh - h];
        for (int i = 1; i <= ltor[x].size(); i++) {
            if (i < r) continue;
            if (i % r == 0) res.push_back(0);
            res.back() += ltor[x][i - 1];
        }
        if (segmax[x] < r) return res;
    }
    for (int i = 0; i < walls.size(); i++) {
        res.push_back(1);
        int x = walls[i] + 1;
        if (x > rb || A[x] == wh) continue;
        x = dsu.find(x);
        int h = height[x];
        if (wh - h > M) return res;
        int r = powL[wh - h];
        for (int i = 1; i <= ltor[x].size(); i++) {
            if (i < r) continue;
            if (i % r == 0) res.push_back(0);
            res.back() += ltor[x][i - 1];
        }
        if (segmax[x] < r) return res;
    }
    return res;
}

vector<int> get_rtol(int lb, int rb, const vector<int> &walls) {
    vector<int> res;
    int wh = A[walls.back()];
    if (rb != walls.back()) {
        int x = dsu.find(rb);
        int h = height[x];
        if (wh - h > M) return res;
        int r = powL[wh - h];
        for (int i = 1; i <= rtol[x].size(); i++) {
            if (i < r) continue;
            if (i % r == 0) res.push_back(0);
            res.back() += rtol[x][i - 1];
        }
        if (segmax[x] < r) return res;
    }
    for (int i = walls.size() - 1; i >= 0; i--) {
        res.push_back(1);
        int x = walls[i] - 1;
        if (x < lb || A[x] == wh) continue;
        x = dsu.find(x);
        int h = height[x];
        if (wh - h > M) return res;
        int r = powL[wh - h];
        for (int i = 1; i <= rtol[x].size(); i++) {
            if (i < r) continue;
            if (i % r == 0) res.push_back(0);
            res.back() += rtol[x][i - 1];
        }
        if (segmax[x] < r) return res;
    }
    return res;
}

int get_segmax(int lb, int rb, const vector<int> &walls) {
    int res = 0;
    int wh = A[walls.front()];
    if (lb != walls.front()) {
        int x = dsu.find(lb);
        int h = height[x];
        if (wh - h > M) return -1;
        int r = powL[wh - h];
        if (segmax[x] < r) return -1;
        res += segmax[x] / r;
    }
    for (int i = 0; i < walls.size(); i++) {
        res++;
        int x = walls[i] + 1;
        if (x > rb || A[x] == wh) continue;
        x = dsu.find(x);
        int h = height[x];
        if (wh - h > M) return -1;
        int r = powL[wh - h];
        if (segmax[x] < r) return -1;
        res += segmax[x] / r;
    }
    return res;
}

void solve() {
    for (int l = 1, r; l <= N; l = r + 1) {
        vector<int> walls = {rnk[l]};
        for (r = l; r < N && A[rnk[r + 1]] == A[rnk[l]] && adjacent(rnk[r + 1], rnk[r]); r++) walls.push_back(rnk[r + 1]);
        int lb = walls.front(), rb = walls.back();
        if (lb > 1 && A[lb - 1] <= A[lb]) lb = dsu.lbound(lb - 1);
        if (rb < N && A[rb + 1] <= A[rb]) rb = dsu.rbound(rb + 1);
        get_ans(lb, rb, walls);
        vector<int> curr_ltor = get_ltor(lb, rb, walls);
        vector<int> curr_rtol = get_rtol(lb, rb, walls);
        int curr_segmax = get_segmax(lb, rb, walls);
        int curr_height = A[walls.front()];
        for (int i = 0; i < walls.size(); i++) {
            if (walls[i] + 1 <= rb)
                dsu.merge(walls[i], walls[i] + 1);
            if (walls[i] - 1 >= lb)
                dsu.merge(walls[i], walls[i] - 1);
        }
        int x = dsu.find(walls.front());
        ltor[x] = curr_ltor;
        rtol[x] = curr_rtol;
        segmax[x] = curr_segmax;
        height[x] = curr_height;
    }
}

void print() {
    printf("%lld\n", ans);
}

int main() {
    init();
    solve();
    print();
}
