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;
int n,k;
int mn[200001],mx[200001];
deque<int>qn,qx;
int a[200001];
int main(){
	ios::sync_with_stdio(false);
	cin >> n >> k;k--;
	int ans=0;
	int st=0;
	int cnt=0;
	for(int i=1; i<=n ;i++){
		cin >> a[i];
		if(i!=1 && a[i]>a[i-1]) cnt++;
		else cnt=0;
		if(cnt>=k && st) ans++;
		else if(i>k+1 && a[qn.front()]>a[i-k-1] && a[qx.front()]<a[i]) ans++;
		if(cnt>=k) st=i;
		if(!qn.empty() && qn.front()==i-k) qn.pop_front();
		if(!qx.empty() && qx.front()==i-k) qx.pop_front();
		while(!qn.empty() && a[qn.back()]>a[i]) qn.pop_back();
		while(!qx.empty() && a[qx.back()]<a[i]) qx.pop_back();
		qn.push_back(i);qx.push_back(i);
	}
	cout << n-k-ans << endl;
}