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>
using namespace std;
const int maxn=200005;
int n,K,a[maxn],ans,flg;
struct ltl{
	int hed,til,Q[maxn];
}A,B;
inline int read(){
	int ret=0;bool f=0;char ch=getchar();
	while(ch>'9'||ch<'0') f^=ch=='-',ch=getchar();
	while(ch<='9'&&ch>='0') ret=ret*10+ch-'0',ch=getchar();
	return f?-ret:ret;
}
int main(){
	n=read(),K=read();ans=n-K+1;
	for (int i=1;i<=n;i++) a[i]=read();
	A.hed=B.hed=1;
	for (int i=1;i<=n;i++){
		while(A.hed<=A.til&&A.Q[A.hed]<i-K) A.hed++;
		while(A.hed<=A.til&&a[A.Q[A.til]]>a[i]) A.til--;
		A.Q[++A.til]=i;
		while(B.hed<=B.til&&B.Q[B.hed]<i-K) B.hed++;
		while(B.hed<=B.til&&a[B.Q[B.til]]<a[i]) B.til--;
		B.Q[++B.til]=i;
		if(A.til-A.hed+(A.Q[A.hed]!=i-K)==K)
		if(!flg) flg=1;else ans--;else
		if(A.Q[A.hed]==i-K&&B.Q[B.hed]==i) ans--;
	}
	printf("%d\n",ans);
	return 0;
}