#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());

template<int N_>
struct Bitset{
	using ULL=unsigned long long;
	static const ULL o=1,inf=(o<<63)-1+(o<<63);
	static const int N=(N_-1)/64+1;
	static const int back_siz=N_-(N-1)*64;
	ULL *a=new ULL[N];
//	ULL a[N];
	void reset(){
		fill(a,a+N,0);
	}
	void set(){
		fill(a,a+N-1,inf);
		a[N-1]=(o<<back_siz-1)-1+(o<<back_siz-1);
	}
	Bitset(const bool& _=0){
		_?set():reset();
	}
	void flip(int x){
		a[x>>6]^=o<<(x&63);
	}
	void reset(int x){
		a[x>>6]&=~(o<<(x&63));
	}
	void set(int x){
		a[x>>6]|=o<<(x&63);
	}
	int test(int x){
		return (a[x>>6]>>(x&63))&1;
	}
	Bitset operator ~() const{
		Bitset ret(N);
		for(int i=0;i<N;i++){
			ret.a[i]=~a[i];
		}
		return ret;
	}
	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;
	}
	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;
	}
	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;
	}
	Bitset operator <<(const int& t) const{
		Bitset ret;
		ULL last=0;
		int high=t>>6,low=t&63;
		for(int i=0;i+high<N;i++){
			ret.a[i+high]=last|(a[i]<<low);
			if(low) last=a[i]>>(64-low);
		}
		return ret;
	}
	Bitset operator >>(const int& t) const{
		Bitset ret;
		ULL last=0;
		int high=t>>6,low=t&63;
		for(int i=N-1;i>=high;i--){
			ret.a[i-high]=last|(a[i]>>low);
			if(low) last=a[i]<<(64-low);
		}
		return ret;
	}
	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=63;j>=0;j--){
				s.push_back('0'+(a[i]>>j&1));
			}
		}
		return s;
	}
	int count() const{
		int ret=0;
		for(int i=0;i<N;i++){
			ret+=__builtin_popcountll(a[i]);
		}
		return ret;
	}
};

#define N 50001

int main(){
	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
*/