#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define pb push_back

typedef long long ll;
//#define int ll

int n, m;
int p[50500];
int q[50500];
bitset<50500> bs[50500];
bitset<50500> b;

#define C 5000

main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin>>n>>m;
    for (int i=1; i<=n; i++)
        cin>>p[i], q[p[i]] = i;

    for (int i=1; i<=n; i++)
        b[i] = 1;
    for (int i=1; i<=n; i++)
    {
        b[q[i]] = 0;
        if (i%C == 0)
        {
            for (int d=1; d<=n-1; d++)
                bs[d] |= (b & ((~b) >> d));
        }
    }
    for (int i=1; i<=n; i++)
        for (int j=i; ; j++)
    {
        if (i!=j)
            if (q[j] < q[i])
                bs[q[i]-q[j]][q[j]] = 1;

        if (j%C == 0)
            break;
    }
    for (int i=1; i+1<=n; i++)
        bs[i] >>= 1;
//    for (int i=1; i+1<=n; i++, cout<<"\n")
//        for (int j=1; j<=n; j++)
//            cout<<bs[i][j];

    ll ans = 0;
    for (int i=1; i+1<=n; i++)
    {
        int D = n-i-m+1;
        if (D <= 0)
            continue;

//        for (int j=0; j<D; j++)
//            cout<<bs[i][j];
//        cout<<"\n";

        int mleft = m-1;
        for (int j=1; mleft > 0; j*=2)
        {
            j = min(j, mleft);
            bs[i] |= (bs[i] << j);
            mleft -= j;
        }

//        for (int j=0; j<D; j++)
//            cout<<bs[i][j];
//        cout<<"\n";

        int all = bs[i].count();
        int lt = (bs[i]>>D).count();
        int ones = all-lt;
        int zeroes = D - ones;
        ans += zeroes;
    }
    cout<<ans<<"\n";
}