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<iostream>
#define RI register int
using namespace std;
const int N=200005;
int n,k,a[N],q[N],cur,ans; bool ismi[N],ismx[N];
int main()
{
	RI i,j,H,T; scanf("%d%d",&n,&k);
	for (i=1;i<=n;++i) scanf("%d",&a[i]);
	for (T=0,q[H=1]=n+1,i=n;i;--i)
	{
		while (H<=T&&q[H]-i>=k) ++H; while (H<=T&&a[i]<a[q[T]]) --T;
		q[++T]=i; if (H==T) ismi[i]=1;
	}
	for (T=0,H=i=1;i<=n;++i)
	{
		while (H<=T&&i-q[H]>=k) ++H; while (H<=T&&a[i]>a[q[T]]) --T;
		q[++T]=i; if (H==T) ismx[i]=1;
	}
	for (i=1;i<=n;i=j+1)
	{
		for (j=i;a[j+1]>a[j];++j); cur+=(j-i+1>=k);
	}
	for (ans=n-k+1-max(cur-1,0),i=k+1;i<=n;++i)
	ans-=ismi[i-k]&&ismx[i]; return printf("%d",ans),0;
}