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 rep(i,n)for(int i=0;i<(n);i++)
using namespace std;
typedef long long ll;
typedef pair<int,int>P;

const int MOD=1000000007;
const int INF=0x3f3f3f3f;
const ll INFL=0x3f3f3f3f3f3f3f3f;

int a[300000];
int main(){
	int n,K;cin>>n>>K;
	rep(i,n)scanf("%d",&a[i]);
	set<int>se;
	deque<P>que;
	int cnt=0;
	rep(i,K){
		se.insert(a[i]);
		if(!que.empty()&&que.back().first>a[i]){
			que.clear();
		}
		que.push_back(P(a[i],i));
	}
	bool F=false;
	if(que.front().second>0){
		cnt=1;
	}
	else F=true;
	for(int i=K;i<n;i++){//[i-K+1,i]
		bool flag=false;
		if(a[i-K]!=*se.begin()){
			flag=true;
		}
		se.erase(a[i-K]);
		if(*se.rbegin()>a[i]){
			flag=true;
		}
		se.insert(a[i]);
		if(!que.empty()&&que.back().first>a[i])que.clear();
		que.push_back(P(a[i],i));
		if(que.front().second>i-K+1){
			cnt+=flag;
		}
		else F=true;
	}
	cout<<cnt+F<<endl;
}