Problem: Snuke has a permutation (P_0,P_1,\cdots,P_{N-1}) of (0,1,\cdots,N-1).

Now, he will perform the following operation exactly once:

* Choose K consecutive elements in P and sort them in ascending order.



Find the number of permutations that can be produced as P after the operation.

Constraints

* 2 \leq N \leq 200000
* 2 \leq K \leq N
* 0 \leq P_i \leq N-1
* P_0,P_1,\cdots,P_{N-1} are all different.
* All values in input are integers.

Input

Input is given from Standard Input in the following format:


N K
P_0 P_1 \cdots P_{N-1}


Output

Print the number of permutations that can be produced as P after the operation.

Examples

Input

5 3
0 2 1 4 3


Output

2


Input

4 4
0 1 2 3


Output

1


Input

10 4
2 0 1 3 7 5 4 6 8 9


Output

6

Solution (in CPP):

Solution:
#include <cstdio>
#include <cstring>
#include <algorithm>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
using namespace std;

int read() {
	char ch;
	for(ch=getchar();ch<'0'||ch>'9';ch=getchar());
	int x=ch-'0';
	for(ch=getchar();ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
	return x;
}

const int N=2e5+5;

int n,k,p[N],mx[N],mn[N],Mx[N],Mn[N],h1,t1,h2,t2;

void push(int x) {
	while (h1<=t1&&p[mx[t1]]<p[x]) t1--;mx[++t1]=x;
	while (h2<=t2&&p[mn[t2]]>p[x]) t2--;mn[++t2]=x;
}

void pop(int x) {
	while (h1<=t1&&mx[h1]<x-k+1) h1++;
	while (h2<=t2&&mn[h2]<x-k+1) h2++;
}

int main() {
	n=read();k=read();
	fo(i,1,n) p[i]=read();
	h1=h2=1;t1=t2=0;
	fo(i,1,k-1) push(i);
	int ans=0;bool fir=1;
	fo(i,k,n) {
		push(i);pop(i);
		Mx[i]=p[mx[h1]];
		Mn[i]=p[mn[h2]];
		if (i>k&&Mx[i]==p[i]&&Mn[i-1]==p[i-k]) continue;
		if (t2-h2+1==k) {ans+=fir;fir=0;continue;}
		ans++;
	}
	printf("%d\n",ans);
	return 0;
}