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

const int N = 1e5 + 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;
}

answer.code: In function ‘int main()’:
answer.code:17:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   17 |         scanf("%d %d", &n, &m);
      |         ~~~~~^~~~~~~~~~~~~~~~~
answer.code:18:38: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   18 |         for(i = 1; i <= n; i++) scanf("%d", &a[i]), p[a[i]] = i;
      |                                 ~~~~~^~~~~~~~~~~~~
/tmp/cclCImA8.o: in function `build(int, int)':
answer.code:(.text+0x31): relocation truncated to fit: R_X86_64_PC32 against symbol `a' defined in .bss section in /tmp/cclCImA8.o
answer.code:(.text+0xaa): relocation truncated to fit: R_X86_64_PC32 against symbol `tr' defined in .bss section in /tmp/cclCImA8.o
answer.code:(.text+0xc0): relocation truncated to fit: R_X86_64_PC32 against symbol `i' defined in .bss section in /tmp/cclCImA8.o
answer.code:(.text+0x1f5): relocation truncated to fit: R_X86_64_PC32 against symbol `i' defined in .bss section in /tmp/cclCImA8.o
/tmp/cclCImA8.o: in function `main':
answer.code:(.text.startup+0x31): relocation truncated to fit: R_X86_64_PC32 against symbol `m' defined in .bss section in /tmp/cclCImA8.o
answer.code:(.text.startup+0x38): relocation truncated to fit: R_X86_64_PC32 against symbol `n' defined in .bss section in /tmp/cclCImA8.o
answer.code:(.text.startup+0x5d): relocation truncated to fit: R_X86_64_PC32 against symbol `n' defined in .bss section in /tmp/cclCImA8.o
answer.code:(.text.startup+0x63): relocation truncated to fit: R_X86_64_PC32 against symbol `i' defined in .bss section in /tmp/cclCImA8.o
answer.code:(.text.startup+0x7b): relocation truncated to fit: R_X86_64_PC32 against symbol `a' defined in .bss section in /tmp/cclCImA8.o
answer.code:(.text.startup+0x89): relocation truncated to fit: R_X86_64_PC32 against symbol `p' defined in .bss section in /tmp/cclCImA8.o
answer.code:(.text.startup+0xa0): additional relocation overflows omitted from the output
collect2: error: ld returned 1 exit status