#include<bits/stdc++.h>
using namespace std;

//#define ONLINE
#ifndef ONLINE
char DEBUG_BUFFER[1000];
#define debug(...) {sprintf(DEBUG_BUFFER,##__VA_ARGS__);\
cerr<<"\033[1;36m"<<DEBUG_BUFFER<<"\033[0;2m"<<"\033[0m";}
#else
#define debug(...) ;
#endif

using LL=long long;
using PII=pair<int,int>;

#define all(x) (x).begin(),(x).end()
#define allr(x) (x).rbegin(),(x).rend()

#define FAST_IO {ios::sync_with_stdio(false);cin.tie(nullptr);}
inline int read(){static int x; cin>>x; return x;}
inline LL readLL(){static LL x; cin>>x; return x;}
mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count());

using u128=__uint128_t;

namespace POPCNT{
	char tab[1<<16];
	inline void init(){
		for(int x=1;x<(1<<16);x++){
			tab[x]=tab[x&(x-1)]+1
		}
	}
	inline int u128_count(const u128& x){
		return tab[x&0xffff]+
		tab[(x>>16)&0xffff]+
		tab[(x>>32)&0xffff]+
		tab[(x>>48)&0xffff]+
		tab[(x>>64)&0xffff]+
		tab[(x>>80)&0xffff]+
		tab[(x>>96)&0xffff]+
		tab[(x>>112)&0xffff];
	}
}
using POPCNT::u128_count;

template<int N_>
struct Bitset{
	static const int N=(N_-1)/128+1,back_siz=N_-(N-1)*128;
	static const u128 o=1,set_last=(o<<back_siz-1)-1+(o<<back_siz-1);
	u128 a[N];
	inline void reset(){
		memset(a,0,sizeof(a));
	}
	inline void set(){
		memset(a,0xff,sizeof(a));
		a[N-1]=set_last;
	}
	inline Bitset(const bool& _=0){
		_?set():reset();
	}
	inline void flip(int x){
		a[x>>7]^=o<<(x&127);
	}
	inline void reset(int x){
		a[x>>7]&=~(o<<(x&127));
	}
	inline void set(int x){
		a[x>>7]|=o<<(x&127);
	}
	inline int test(int x){
		return (a[x>>7]>>(x&127))&1;
	}
	inline Bitset operator ~() const{
		Bitset ret(N);
		for(int i=0;i<N;i++){
			ret.a[i]=~a[i];
		}
		return ret;
	}
	inline Bitset operator &(const Bitset &b) const{
		Bitset ret(N);
		for(int i=0;i<N;i++){
			ret.a[i]=a[i]&b.a[i];
		}
		return ret;
	}
	inline Bitset operator |(const Bitset &b) const{
		Bitset ret;
		for(int i=0;i<N;i++){
			ret.a[i]=a[i]|b.a[i];
		}
		return ret;
	}
	inline Bitset operator ^(const Bitset &b) const{
		Bitset ret;
		for(int i=0;i<N;i++){
			ret.a[i]=a[i]^b.a[i];
		}
		return ret;
	}
	inline Bitset operator <<(const int& t) const{
		Bitset ret;
		u128 last=0;
		int high=t>>7,low=t&127;
		for(int i=0;i+high<N;i++){
			ret.a[i+high]=last|(a[i]<<low);
			if(low) last=a[i]>>(128-low);
		}
		return ret;
	}
	inline Bitset operator >>(const int& t) const{
		Bitset ret;
		u128 last=0;
		int high=t>>7,low=t&127;
		for(int i=N-1;i>=high;i--){
			ret.a[i-high]=last|(a[i]>>low);
			if(low) last=a[i]<<(128-low);
		}
		return ret;
	}
	inline string str() const{
		string s="";
		for(int j=back_siz-1;j>=0;j--){
			s.push_back('0'+(a[N-1]>>j&1));
		}
		for(int i=N-2;i>=0;i--){
			for(int j=127;j>=0;j--){
				s.push_back('0'+(a[i]>>j&1));
			}
		}
		return s;
	}
	inline int count() const{
		int ret=0;
		for(int i=0;i<N;i++){
			ret+=u128_count(a[i]);
		}
		return ret;
	}
};

#define N 50001

int main(){
	POPCNT::init();
	FAST_IO;
	int n=read(),m=read();
	vector<int>pos(n);
	for(int i=0;i<n;i++){
		pos[read()-1]=i;
	}
	vector<Bitset<N>>f(n),suf(m);
	Bitset<N>tmp;
	for(int x=n-1;x>=0;x--){
		f[pos[x]]=tmp>>pos[x];
		tmp.set(pos[x]);
	}
	LL ans=0;
	for(int i=0,last=-1;i<n-m+1;i++){
		if(i>last){
			last+=m;
			suf[0]=f[last];
			for(int j=1;j<m;j++){
				suf[j]=suf[j-1]&f[last-j];
			}
			tmp.set();
		}
		ans+=(suf[last-i]&tmp).count();
		if(i+m<n) tmp=tmp&f[i+m];
	}
	cout<<ans;
	return 0;
}

/* stuff you should look for
* int overflow, array bounds
* special cases (n=1?)
* do smth instead of nothing and stay organized
* WRITE STUFF DOWN
* DON'T GET STUCK ON ONE APPROACH
*/

answer.code: In function ‘void POPCNT::init()’:
answer.code:30:46: error: expected ‘;’ before ‘}’ token
   30 |                         tab[x]=tab[x&(x-1)]+1
      |                                              ^
      |                                              ;
   31 |                 }
      |                 ~