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 main() {
  int n, k;
  cin >> n >> k;
  vector<int> a(n);
  for (auto& e : a) cin >> e;

  int r = n - k + 1;

  vector<int> c(n);
  c[n - 1] = 1;
  for (int i = n - 2; i >= 0; i--) c[i] = a[i] < a[i + 1] ? c[i + 1] + 1 : 1;
  int t = 0;
  for (auto e : c) t += e >= k;
  r -= max(0, t - 1);

  set<int> s;
  for (int i = 0; i < k; i++) s.insert(a[i]);
  for (int i = 0; i + k < n; i++) {
    r -= c[i] < k && a[i] == *s.begin() && a[i + k] > *s.rbegin();
    s.erase(a[i]);
    s.insert(a[i + k]);
  }

  cout << r << endl;
}