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;
#define int long long 

signed main(void){ 
  int N,K; cin >> N >> K;
  vector<int> P(N);
  for(int i = 0; i < N; i++){ cin >> P[i];}
  
  vector<int> a(N,0); 
  vector<int> sum(N,0);
  
  for(int i = 1; i < N; i++){ 
    if( P[i] > P[i-1] ){ a[i]++;}
  }
  
  for(int i = 1; i < N; i++){ 
    sum[i] = sum[i-1]+a[i];
  }
  
  bool sorted = (sum[K-1]==K-1);
  
  set<int> S;
  
  for(int i = 0; i < K; i++){ S.insert(P[i]);}
  
  int cnt = !sorted;
  
  // P[i]~P[i+K-1]とP[i+1]~P[i+K]を比較して異なるかを調べる
  
  for(int i = 0; i < N-K; i++){ 
    // P[i]が出て行って、P[i+K]が入ってくる
    
    bool l = (*S.begin() == P[i] );
    S.erase(P[i]);
    S.insert(P[i+K]);
    bool r = (*S.rbegin() == P[i+K]);
    
    if( sum[i+K]-sum[i+1] == K-1 ){ sorted = true;}
    else{ 
      if( !(l&&r) ){ //この時、２つは異なる
        cnt++; 
      }
    }
  }
  
  cout << cnt+sorted << endl;
  
  return 0;
}