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 <iostream>
#include <set>

using namespace std;

int n, k;
int a[202020];
int s[202020];
set<int> f;

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> k;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		s[i] = s[i-1];
		if (i != 1) s[i] += a[i] < a[i-1];
	}
	for (int i = 1; i <= k; i++) f.insert(a[i]);
	int c = 1;
	int z = 0;
	if (s[k] == s[1]) z++;
	for (int i = k+1; i <= n; i++) {
		f.insert(a[i]);
		int x1 = *f.begin();
		int x2 = *f.rbegin();
		bool ok = true;
		if (x1 == a[i-k] && x2 == a[i]) ok = false;
		if (ok) {
			if (s[i] == s[i-k+1]) z++;
			c++;
		}
		f.erase(a[i-k]);
	}
	if (z > 1) c -= (z-1);
	cout << c << "\n";
}