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

const int N = 5e4 + 7;
int i, j, k, n, m, l, r;
int a[N], p[N], tr;
bitset<N> u[N], t[N], w, s, v;
ll res;

void build(int l, int r) {
	t[r] = u[a[r]]; tr = r; w.set();
	for(i = r - 1; i >= l; i--) t[i] = (t[i + 1] >> 1) & u[a[i]];
}

int main() {
	scanf("%d %d", &n, &m);
	for(i = 1; i <= n; i++) scanf("%d", &a[i]), p[a[i]] = i;
	for(i = 1; i <= n; i++) u[i + 1] = u[i], u[i + 1][p[i]] = 1;
	for(i = 1; i <= m; i++) v[i] = 1;
	l = 1, r = m; build(l, r);
	while(r < n) {
		++l, ++r;
		if(l > tr) {
			build(l, r);
			s = t[l];
		} else {
			w = w & (u[a[r]] >> r - tr);
			s = t[l] & (w >> tr - l);
		}
//		s &= v;
//		v[l] = 1;
		res += s.count();
	}
	printf("%lld\n", res);
	return 0;
}