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>
#define aaa(i,n) for ((i)=1;(i)<=(n);(i)++)
#define bbb(i,x,y) for ((i)=(x);(i)<=(y);(i)++)
using namespace std;
int n,m,i,j,f[200005][19],g[200005][19],a[200005],l[200005],lg[200005],t,ans,ys;int qrymi(int x,int y){int k=lg[y-x+1];return min(f[x][k],f[y-(1<<k)+1][k]);}int qrymx(int x,int y){	int k=lg[y-x+1];	return max(g[x][k],g[y-(1<<k)+1][k]);}
int main(){bbb(i,2,200000){		lg[i]=lg[i/2]+1;	}	scanf("%d%d",&n,&m);	aaa(i,n){		scanf("%d",&a[i]);		g[i][0]=f[i][0]=a[i];	}
	aaa(j,18)aaa(i,n-(1<<j)+1){		f[i][j]=min(f[i][j-1],f[i+(1<<(j-1))][j-1]);		g[i][j]=max(g[i][j-1],g[i+(1<<(j-1))][j-1]);	}	aaa(i,n){		if(i>1&&a[i-1]<a[i]) l[i]=l[i-1]+1; else l[i]=1;	}
	if(l[m]>=m) ys=1; else ans=1;	bbb(i,m+1,n){		if(l[i]>=m){			ys=1;			continue;		}		if(qrymi(i-m,i)==a[i-m]&&qrymx(i-m,i)==a[i]){			continue;
		}		else{			ans++;		}	}	cout<<ans+ys<<endl;	return 0;}