#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>

using std::ios_base, std::cin, std::cout;
using std::vector, std::set, std::map, std::bitset;
using std::views::iota, std::views::reverse;

template <class T> using Vec = vector<T>;

constexpr int MAXN = 50010;
using Bitset = std::bitset<MAXN>;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << std::fixed << std::setprecision(20);

    int N, M;
    cin >> N >> M;
    Vec<int> P(N);
    for (int& a : P) {
        cin >> a;
        a--;
    }
    Vec<int> invP(N);
    for (int i : iota(0, N)) {
        invP[P[i]] = i;
    }

    auto mat = Vec<Bitset>(N);  // mat[i][d] := [P[i] < P[i + d]]

    {
        auto larger = Bitset{};
        for (int p : iota(0, N) | reverse) {
            int i = invP[p];
            mat[i] = larger >> i;
            larger.set(i);
        }
    }

    int64_t ans = 0;
    auto prefix = Bitset{};
    for (int l = 0; l + M <= N; l += M) {
        for (int i : iota(l, l + M - 1) | reverse) {
            mat[i] &= mat[i + 1];
        }
        prefix.set();
        for (int r : iota(l + M, l + 2 * M)) {
            ans += (prefix & mat[r - M]).count();
            if (r == N) break;
            prefix &= mat[r];
        }
    }
    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:2:
/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
      |              ^~~~~~~~~~~~