#pragma GCC optimize("O3")
#pragma GCC target("popcnt")
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

constexpr int N = 5e4;

using B = bitset<N>;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    vector<int> p(n);
    for (int i = 0; i < n; ++i) {
        cin >> p[i];
        --p[i];
    }

    vector<B> a(n);
    vector<int> ord(n);
    iota(ord.begin(), ord.end(), 0);
    sort(ord.begin(), ord.end(), [&](int i, int j) {
        return p[i] < p[j];
    });
    B tmp{};
    for (int i = 0; i < n; ++i) {
        a[ord[i]] = tmp;
        tmp[ord[i]] = 1;
    }
    tmp = 0;
    for (int i = 0; i < n; ++i) {
        a[i] &= tmp;
        tmp[i] = 1;
        a[i] <<= n - i;
    }

    vector<B> suf(n), pref(n);
    for (int sep = m; sep <= n; sep += m) {
        B g = a[sep - 1];
        for (int i = sep - 1; i >= sep - m; --i) {
            if (i != sep - 1) {
                g &= a[i];
            }
            suf[i] = g;
        }
        if (sep < n) {
            g = a[sep];
            for (int i = sep; i < min(n, sep + m); ++i) {
                if (i != sep) {
                    g &= a[i];
                }
                pref[i] = g;
            }
        }
    }

    ll ans = 0;
    int sep = m;
    for (int i = 0; i + m <= n; ++i) {
        while (sep <= i) {
            sep += m;
        }
        B now = suf[i];
        if (sep < i + m) {
            now &= pref[i + m - 1];
        }
        ans += now.count();
    }
    cout << ans << '\n';

    return 0;
}

In file included from /usr/include/c++/13/string:43,
                 from /usr/include/c++/13/bitset:52,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:52,
                 from answer.code:3:
/usr/include/c++/13/bits/allocator.h: In destructor ‘constexpr std::_Vector_base<int, std::allocator<int> >::_Vector_impl::~_Vector_impl()’:
/usr/include/c++/13/bits/allocator.h:184:7: error: inlining failed in call to ‘always_inline’ ‘constexpr std::allocator< <template-parameter-1-1> >::~allocator() noexcept [with _Tp = int]’: target specific option mismatch
  184 |       ~allocator() _GLIBCXX_NOTHROW { }
      |       ^
In file included from /usr/include/c++/13/vector:66,
                 from /usr/include/c++/13/functional:64,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:53:
/usr/include/c++/13/bits/stl_vector.h:133:14: note: called from here
  133 |       struct _Vector_impl
      |              ^~~~~~~~~~~~