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

struct Bitset{
	using ULL=unsigned long long;
	static const ULL o=1;
	vector<ULL>a;
	int N,back_siz;
	void reset(){
		a.assign(N,0);
	}
	void set(){
		a.assign(N,1);
		a.back()=(o<<back_siz)-1;
	}
	Bitset(const int& N_=0,const bool& _=0){
		N=(N_-1)/64+1;
		back_siz=N_-(N-1)*64;
		_?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;
	}
	char* str() const{
		string s="";
		for(int i=N-1;i>=0;i--){
			for(int j=63;j>=0;j--){
				s.push_back('0'+(a[i]>>j&1));
			}
		}
		return s.data();
	}
	int count() const{
		int ret=0;
		for(auto x:a){
			debug("\t%llu %d\n",x,__builtin_popcountll(x));
			ret+=__builtin_popcountll(x);
		}
		return ret;
	}
};

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 f(n,Bitset(n+1));
	vector suf(m,Bitset(n+1));
	Bitset tmp(n+1);
	for(int x=n-1;x>=0;x--){
		f[pos[x]]=tmp>>pos[x];
		tmp.set(pos[x]);
	}
#ifndef ONLINE
	for(int i=0;i<n;i++){
		debug("f[%d]=%s\n",i+1,f[i].str());
	}
#endif
	LL ans=0;
	for(int i=0,last=-1;i<n-m+1;i++){
		debug("i=%d\n",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];
			}
#ifndef ONLINE
			debug("update suf\n");
			debug("\tlast=%d\n",last+1);
			for(int j=0;j<m;j++){
				debug("suf[%d]=%s\n",j+1,suf[j].str());
			}
#endif
			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
*/