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>
#include <algorithm>
#include <cstring>
#include <set>
#define ll long long
using namespace std;
template <class T>
inline void rd(T &x)
{
	x=0; char c=getchar(); int f=1;
	while(!isdigit(c)){if(c=='-')f=-1; c=getchar();}
	while(isdigit(c)) x=x*10-'0'+c,c=getchar(); x*=f;
}
const int N=2e5+10;
set<int> s;
int a[N],n,k;
int vis[N];
int main() {
	rd(n),rd(k);
	for(int i=1;i<=n;++i) rd(a[i]);
	int ans=n-k+1,flg=0;
	int cnt=0;
	for(int i=1;i<k;++i) cnt+=a[i+1]>a[i];
	for(int i=1;i<=n-k+1;++i) {
		if(cnt==k-1) vis[i]=1,ans--,flg=1;
		cnt-=a[i+1]>a[i];
		cnt+=a[i+k]>a[i+k-1];
	}
	for(int i=1;i<=k;++i) s.insert(a[i]);
	for(int i=1;i<n-k+1;++i) {
		s.insert(a[i+k]);
		if(!vis[i]&&!vis[i+1]) {
			if((*s.begin())==a[i]&&(*s.rbegin())==a[i+k]) ans--;
		}
		s.erase(a[i]);
	}
	printf("%d",ans+flg);
	return 0;
}