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;
struct Node {int l, r, x;};
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, l;
    cin >> n >> l;
    vector<int> a(n);
    for (int i = 0; i < n; ++i)
        cin >> a[i];
    struct Node {
        int pre, nxt, val, l, r;
        bool isNew;
    };
    vector<Node> t(n);
    vector<pair<int, int>> s;
    for (int i = 0; i < n; ++i) {
        t[i].pre = i - 1;
        t[i].nxt = i == n - 1 ? -1 : i + 1;
        t[i].l = t[i].r = 1;
        t[i].val = a[i];
        t[i].isNew = false;
        s.emplace_back(a[i], i);
    }
    sort(s.begin(), s.end(), greater<pair<int, int>>());
    long long ans = 0;
    auto connect = [&](int l, int r) {
        if (l != -1)
            t[l].nxt = r;
        if (r != -1)
            t[r].pre = l;
    };
    while (!s.empty()) {
        int x = s.back().first;
        vector<int> v, v1;
        while (!s.empty() && s.back().first == x) {
            int p = s.back().second;
            if (t[p].pre == -1 || t[t[p].pre].val != x)
                v.push_back(p);
            if ((t[p].pre == -1 || t[t[p].pre].val != x || !t[t[p].pre].isNew) && t[p].isNew)
                v1.push_back(p);
            s.pop_back();
        }
        for (int p : v1) {
            vector<int> ver;
            for (int i = p; ; i = t[i].nxt) {
                if (i == -1 || t[i].val != x || !t[i].isNew)
                    break;
                ver.push_back(i);
            }
            int sum = 0;
            for (int i = l - 1; i < (int)ver.size(); ++i) {
                sum += t[ver[i - l + 1]].l;
                ans -= 1LL * sum * t[ver[i]].r;
            }
        }
        for (int p : v) {
            vector<int> ver;
            for (int i = p; ; i = t[i].nxt) {
                if (i == -1 || t[i].val != x)
                    break;
                ver.push_back(i);
            }
            if ((int)ver.size() < l) {
                connect(t[p].pre, -1);
                connect(-1, t[ver.back()].nxt);
                continue;
            }
            int sum = 0;
            for (int i = l - 1; i < (int)ver.size(); ++i) {
                sum += t[ver[i - l + 1]].l;
                ans += 1LL * sum * t[ver[i]].r;
            }
            int cnt = ver.size() / l;
            vector<int> newL(cnt), newR(cnt);
            for (int i = l - 1; i < (int)ver.size(); ++i) {
                newL[cnt - (i - l + 1) / l - 1] += t[ver[ver.size() - i - 1]].l;
                newR[(i - l + 1) / l] += t[ver[i]].r;
            }
            int lst = t[p].pre;
            for (int i = 0; i < cnt; ++i) {
                ++t[ver[i]].val;
                t[ver[i]].isNew = true;
                t[ver[i]].l = newL[i];
                t[ver[i]].r = newR[i];
                connect(lst, ver[i]);
                s.emplace_back(t[ver[i]].val, ver[i]);
                lst = ver[i];
            }
            connect(lst, t[ver.back()].nxt);
        }
    }
    cout << ans + n << endl;
    return 0;
}