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<bits/stdc++.h>
using namespace std;
struct node
{
	int v,id;
	node(int x1=0,int x2=0){v=x1,id=x2;}
};
deque<node>q1,q2;
int a[500001];
int l[500001];
signed main()
{
	int n,k;
    scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	for(int i=1;i<=n;i++)
		l[i+1]=(a[i+1]>a[i])?1:0;
	a[0]=999999999;
	int flag=0,ans=0,sum=0;
	for(int i=1;i<=n;i++)
	{
		while(!q1.empty()&&q1.back().v<=a[i])
			q1.pop_back();
		while(!q2.empty()&&q2.back().v>=a[i])
			q2.pop_back();
		while(!q1.empty()&&i-q1.front().id>=k)
			q1.pop_front();
		while(!q2.empty()&&i-q2.front().id>=k)
			q2.pop_front();
		q1.push_back(node(a[i],i));
		q2.push_back(node(a[i],i));
		sum+=l[i];
		if(i>=k)
			sum-=l[i-k+1];
		if(i<k||(a[i+1]>q1.front().v&&a[i-k+1]==q2.front().v))
			continue;
		if(sum==k-1)
		{
			if(flag)
				continue;
			flag=1;
		}
		ans++;
	}
	printf("%d",ans);
	return 0;
}